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

Verilmiş çəkili və istiqamətsiz qrafda, kənarların çəkiləri 1, 1/2, 1/3, 1/4-dür. 1 zirvəsindən digər zirvələrə qədər ən qısa yolu tapın.

Giriş məlumatları

Birinci sətirdə qrafın zirvələrinin və kənarlarının sayı olan iki natural ədəd n və m (1 ≤ n ≤ 10^6, 1 ≤ m ≤ 8 * 10^5) verilmişdir. Sonrakı sətirlərdə kənarlar təsvir olunur. Hər bir kənar üç natural ədəd ilə göstərilir: u, v və w (1 ≤ u, v ≤ n, u ≤ v, 1 ≤ w ≤ 4), bu da u-dan v-yə qədər 1/w çəkisi olan kənarın mövcudluğunu ifadə edir.

Çıxış məlumatları

Hər bir zirvə üçün 2-dən n-ə qədər bir ədəd çıxarın - 1 zirvəsindən ona qədər ən qısa yolun uzunluğu, ən az 8 onluq dəqiqliklə.

Nümunələr