Biliklərə gedən yol
Vasya universitetdə oxuyur və hər gün ora piyada gedir. Vasya'nın yaşadığı şəhər istiqamətsiz qraf şəklində təsvir olunur. Vasya yol seçməkdə elmi yanaşma tətbiq etmək qərarına gəldi, buna görə şəhərin xəritəsini öyrəndi və evdən universitetə qədər olan bütün ən qısa marşrutları tapdı. İndi hər dəfə Vasya universitetə və ya geri gedəndə, bu marşrutlardan birini seçir və hər marşrut bərabər ehtimalla seçilir.
Bir neçə gündən sonra Vasya bəzi kəsişmələrdən daha çox keçdiyini fərq etdi. O, hər kəsişmədən gündə orta hesabla neçə dəfə keçdiyini hesablamağa qərar verdi. Lakin, o, təhsillə məşğul olduğundan, bunu sizə tapşırdı.
Giriş verilənləri
Giriş faylının ilk sətiri Vasya'nın yaşadığı şəhərdəki kəsişmələrin və yolların sayını göstərən iki tam ədəd N və M ehtiva edir.
Növbəti M sətirdən hər biri bir küçəyə uyğun gəlir və üç tam ədəd Ai, Bi və Li ehtiva edir — küçənin birləşdirdiyi kəsişmələrin nömrələri və onun uzunluğu kilometrdə.
Vasya'nın evi birinci kəsişmənin yanında, universitet isə N-ci kəsişmənin yanındadır. Vasya'nın evindən universitetə yollarla getmək mümkün olduğu təmin edilir.
1 ≤ N ≤ 10^5
0 ≤ M ≤ 10^5
1 ≤ Ai, Bi ≤ N
1 ≤ Li ≤ 10000
Çıxış verilənləri
Birinci kəsişmədən N-ci kəsişməyə qədər olan kəsişmələrdən gündə orta keçid sayını göstərən N ədəd çıxarın. Ədədləri 10^{−7} dəqiqliklə çıxarın. Unutmayın ki, Vasya şəhərdə gündə iki dəfə — universitetə və geri gedir.