Etibarlı marşrut#4457
Şəhərdə bəzi küçələrin keçilməsi, tez-tez təmir işləri, sıx hərəkət və ya ara-sıra bağlanmaları kimi səbəblərlə xüsusilə əlverişsiz olduğu məlumdur. Bələdiyyə hesabatlarını təhlil etdikdən sonra şəhər planlaşdırıcısı müəyyən edib ki, verilmiş bir küçənin müəyyən bir gündə keçilməz və ya problemli olma ehtimalı (faizlə ifadə olunub) nə qədərdir.
Planlaşdırıcının məqsədi evindən şəhər meriyasına gündəlik yolçuluğu üçün ən etibarlı marşrutu tapmaqdır. Konkret olaraq, o, yol boyu qarşısına keçilməz küçə çıxma ehtimalını minimuma endirən evindən başlayıb şəhər meriyasında bitən bir marşrut tapmaq istəyir.
Girişin birinci sətrində iki tam ədəd və verilir: binaların və bu binaları birləşdirən küçələrin sayı (1 \leq N \leq 100, 1 \leq M \leq \frac{N(N-1)}{2}). İkinci sətrdə planlaşdırıcının yaşadığı bina və şəhər meriyasının yerləşdiyi bina nömrələrini göstərən iki tam ədəd və verilib. Növbəti sətrin hər birində üç tam ədəd var: S_i, F_i və P_i. Bunlar müvafiq olaraq küçənin başladığı və bitdiyi bina nömrələrini və küçənin müəyyən bir gündə keçilməz və ya problemli olma ehtimalını (faizlə) göstərir (1 \leq S_i \leq N, 1 \leq F_i \leq N, 0 \leq P_i \leq 100). Bütün küçələr ikitərəflidir. Evdən meriyaya ən azı bir yolun olması təmin edilir.
Yolda qarşıya çıxacaq keçilməz və ya problemli küçənin ən kiçik mümkün ehtimalını (faizlə) çıxış edin, ən azı 6 onluq dəqiqliklə.
Nümunə 1