#5 레몬 경로

Statement

Statement language

I like Dijkstra more than Bellman-Ford... But what should I do if I like BFS even more than Dijkstra?

Generally, in an undirected graph with weighted edges, the shortest path refers to the path with the minimum sum of edge weights. However, Jaewon, who loves BFS too much, wants to minimize the number of edges included in the path.

We define any path that minimizes the number of edges to be "Lemon Path". The weight of a Lemon Path is defined as the sum of the weights of the edges included in that path, and the "Lemon Distance" between two vertices is defined to be the average of the weights of all Lemon Paths connecting two vertices.

A connected graph with $N$ vertices and $M$ bidirectional edges is given. The $i$ -th edge connects $U_i$ and $V_i$ , and its weight is .

Find the Lemon Distance between vertex $1$ and all other vertices. The graph may contain self-loops or multiple edges.

Input

The input is given in the following format.

$N \ M$ $U_1 \ V_1 \ C_1$

Output

From the first line, print the Lemon Distance between vertex $1$ and vertex $i+1$ on the $i$ -th line over $N-1$ lines, using the following method.

If the Lemon Distance is where and are coprime positive integers, print a positive integer such that and . Also, it is guaranteed that the number of Lemon Paths between vertex and other vertex is never a multiple of .

Constraints

$2 \le N \leq 100\ 000$ .
$1 \le M \leq 500\ 000$ .
$1 \leq U_{i}$ ().

Subtasks

#	Score	Constraints
1	6	The graph is a complete graph. In other words, there is exactly one edge connecting any two different vertices.
2	13	The weight of all edges is $1$ .
3	16	$N \le 10, M \le 20$ .
4	28	.

Samples

Input

Output

The given graph can be represented as the figure above. For each vertex, the Lemon Distance is calculated as follows.

The only Lemon Path between vertex $1$ and vertex $2$ is $(1, 2)$ , and the Lemon Distance is $\dfrac{0}{1}=0$ .