There are n nodes(1,2.. n) in a weighted graph with m (m>n) bi-directional edges. All weights are positive and there are no multiple edges. There is one fixed origin(Node 1). We will always start traveling from the origin. Now we have to find number of ways to reach each of the nodes(starting from the origin) with minimum cost. Expected complexity O(m*log(m)). Input — First line contains n , m . Next m lines contains u,v,w. => There is edge between u and v of weight w(w>0).

Output — Print n-1 lines one for each nodes other than origin, containing the number of ways to reach each of the nodes(starting from the origin) with minimum cost.

Sample Test — 4 5 1 2 5 1 3 3 3 2 2 3 4 7 2 4 5