Qrafik 1, 1/2, 1/3, 1/4

Giriş

Birinci sətirdə $n$ və $m$ tam ədədləri verilir ( $1 \leq n \leq 1 0^{6}$ 1 \leq n \leq 10^6, $1 \leq m \leq 8 \times 1 0^{5}$ 1 \leq m \leq 8 \times 10^5) — qrafın zirvələrinin və kənarlarının sayı. Kənarların hər biri ayrıca sətirdə verilir. Hər kənar üçün üç tam ədəd: $u$ , $v$ və $w$ ( $1 \leq u, v \leq n$ 1 \leq u, v \leq n, $u \leq v$ u \leq v, $1 \leq w \leq 4$ 1 \leq w \leq 4) verilir, yəni $u$ və $v$ zirvələri arasında çəkisi $\frac{1}{w}$ \dfrac{1}{w} olan yöndsüz kənar var.

Çıxış

Hər bir $2$ -dən $n$ -ə kimi zirvələr üçün bir ədəd çap edin — 1-ci zirvədən həmin zirvəyə ən qısa yolun uzunluğunu ən azı $8$ onluq kəsr dəqiqliyilə verin.

Nümunələr

Nümunə 1

Loading