Competitions

Graph 1, 1/2, 1/3, 1/4

Given connected, directed graph with edge weights 1, 1/2, 1/3, 1/4. Find the shortest path from vertex 1 to all others.

Input

The first line contains two integers n and m (1n5 *105, 1m8 *105) - the number of vertices and edges in a graph. The edges are given on separate lines. The edges are given with three integers: u, v и w (1u, vn, uv, 1w4), meaning the directed edge from u to v with weight 1/w.

Output

For each vertex from 2 to n print one number - the length of the shortest path from vertex 1 to it with no less than 8 digits after the decimal point.

Time limit 1 second
Memory limit 128 MiB
Input example #1
4 4
1 2 1
2 3 2
3 4 4
4 1 3

Output example #1
1.00000000
0.58333333
0.33333333