"Blyuz qardaşları" filmində, Elvud və Cekin tərbiyə aldıqları uşaq evi, əgər onlar Kukun Çikaqodakı ofisinə 5000 dollar vergi ödəməsələr, Təhsil Şurasına satılmalıdır. Onlar Palas Oteldə konsert verməklə 5000 dollar qazanaraq Çikaqoya yol tapmalıdırlar. Lakin, bu elə də asan deyildir. Çünki, onları polis, yerli banda və millətçi qrup təqib edir. Üstəlik də, artıq hava qaralır, onlar qara eynək taxır, Çikaqoya qədər isə 106 mil məsafə var.

Onların İlahi missiyası olduğunu nəzərə alaraq onlara ən təhlükəsiz yol tapmaqda kömək edin. Ən təhlükəsiz yol, tutulmamaq ehtimalı ən böyük olan yoldur.

Giriş verilənləri

Birinci sətirdə iki ədəd yazılır: n (2 ≤ n ≤ 100) və m (1 ≤ m ≤ n · (n - 1) / 2), n - yolayırıcılarının sayı, m - küçələrin sayı.

Sonrakı m sətrin hər birində üç ədəd: a, b və p (1 ≤ a, b ≤ n, a ≠ b, 1 ≤ p ≤ 100) yazılır. Burada a və b - küçələrin ücları, p isə Blyuz qardaşlarının həmin küçədən gizli keçmə ehtimalıdır (faizlə). Bütün küçələr ikitərəflidir və istənilən iki yolayırıcı arasında küçə sayı birdən çox deyil.

Çıxış verilənləri

1 (Palas Otel)–dən n–ci yolayırıcına qədər ən təhlükəsiz yolun ələ keçməmə ehtimalını hesablayın və elə hesab edin ki, bu cür yol mövcuddur.

Axtarılan ehtimalı vergüldən sonra 6 rəqəm dəqiqliyi ilə faizlə çıxarın. Cavabı aşağıda göstərilən formatda çıxarmaq lazımdır.

Göstəriş

Ən təhlükəsiz yol: 1 → 4 → 3 → 5 olar.