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

Input

The first line contains two integers $n$ and $m$ (1 \leq n \leq 10^6, 1 \leq m \leq 8 \times 10^5) — the number of vertices and edges in the graph. The edges are given on separate lines. Each edge is given with three integers: $u$, $v$ and $w$ (1 \leq u, v \leq n, u \leq v, 1 \leq w \leq 4), meaning that there is an undirected edge between $u$ and $v$ with weight \dfrac{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 at least $8$ digits after the decimal point.

Examples