Təhlükəli marşrut
Professor Dijkstra şəhərin təhlükəli bir rayonunda yaşayır. Hər gün banditlər küçələrdə keçənləri qarət edirlər. Cinayət xronikasını araşdıraraq, professor hər küçədən keçərkən qarət olunma ehtimalını hesablayıb.
İndi o, evindən dərs dediyi universitetə ən təhlükəsiz yolu tapmaq istəyir. Başqa sözlə, o, evindən universitetə qarət olunma ehtimalının ən az olduğu yolu müəyyənləşdirmək istəyir.
Giriş verilənləri
Giriş faylının ilk sətirində N və M - binaların sayı və binaları birləşdirən küçələrin sayı (1 ≤ N ≤ 100, 1 ≤ M ≤ N(N-1)/2) verilmişdir. Növbəti sətirdə iki ədəd S və F - professorun yaşadığı evin və universitetin yerləşdiyi binanın nömrəsi verilmişdir. Daha sonra M sətirdə yolların təsviri verilmişdir: 3 tam ədəd S_i, F_i və P_i - yolun başladığı və bitdiyi binaların nömrələri və yoldan keçərkən qarət olunma ehtimalı faizlə (1 ≤ S_i ≤ N, 1 ≤ F_i ≤ N, 0 ≤ P_i ≤ 100, yollar ikitərəflidir). Professorun evindən universitetə ən azı bir yolun mövcud olduğu təmin edilir.
Çıxış verilənləri
Bir ədəd - qarət olunma ehtimalının mümkün olan ən kiçik dəyərini ən azı 6 ondalık dəqiqliklə çıxış edin.