Time limit: 500ms
Memory limit: 256mb

Description:
Change  a classic dijkstra algorithm to do path counting in an undirected graph.
Given a source node, output the number of shortest paths from source to other nodes.

-------------------------Copy the following code, complete it and submit-------------------------


/*
I, , am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>


#define MAX_NODES 100

int graph[MAX_NODES][MAX_NODES];
int dist[MAX_NODES];
int count[MAX_NODES];
int visited[MAX_NODES];


void path_counting(int src, int V)
{
	// write down your code here
}

int main()
{

	for (int i = 0; i < MAX_NODES; i++) {
		for (int j = 0; j < MAX_NODES; j++) {
			graph[i][j] = 0;
		}
	}
	
	int n, m;
	scanf("%d %d",&n, &m);
	int src;
	scanf("%d", &src);
	
	int x, y;
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &x, &y);
		scanf("%d", &graph[x][y]);
		graph[y][x] = graph[x][y];
	}
	
	
	path_counting(src, n);
	
	return 0;
}



-------------------------------------------End of Code-------------------------------------------

Input:
The number of nodes.
The number of edges.
The source node.
The edges with given weights in an undirected graph.

Output:
The number of paths from source to different nodes(The number of paths from source to itself should be 1).

Sample Input 1:
8 9 1
0 1 1
1 2 2
1 3 1
2 3 2
3 4 1
4 5 2
5 6 1
6 7 2
3 7 6


Sample Output 1:
Number of paths from node 1 to node 0 is: 1
Number of paths from node 1 to node 1 is: 1
Number of paths from node 1 to node 2 is: 1
Number of paths from node 1 to node 3 is: 1
Number of paths from node 1 to node 4 is: 1
Number of paths from node 1 to node 5 is: 1
Number of paths from node 1 to node 6 is: 1
Number of paths from node 1 to node 7 is: 2