Piyada və velosipedçi
İki nəfərdən ibarət bir komanda həyat haqqında söhbət edərkən vaxtın necə keçdiyini hiss etmədi. Birdən, proqramlaşdırma üzrə dünya çempionatının dörddəbir finalına gecikdiklərini və şəhərin digər ucunda olduqlarını anladılar. Xoşbəxtlikdən, onlardan birinin velosipedi var idi. Lakin yarış qaydalarına görə, komandanın bütün üzvləri bir araya gəlmədən yarışa buraxılmırlar. Buna görə də, komandanın son üzvünün nə vaxt gələcəyi vacibdir. Əgər onlardan biri velosipedə minib sona çatsa, o biri bütün yolu piyada getməli olacaq. Hər ikisi velosiped sürməyi eyni dərəcədə bacarır, buna görə də eyni sürətlə gedirlər. Təəssüf ki, onlar iki nəfər bir velosipeddə sürə bilmirlər.
Oğlanlar tez bir sxem hazırladılar ki, yarışın keçirildiyi yerə necə çatmaq olar. Sxem N kəsişmə və onları birləşdirən M yoldan ibarət idi. Onlar hər bir yol üçün tək istiqamət seçdilər ki, hansısa kəsişmədən çıxdıqdan sonra artıq ora qayıda bilməsinlər. Dostlar tez başa düşdülər ki, bir yol qət etdikdən sonra piyada gedib velosipedi buraxmaq olar ki, hazırda piyada gedən digər şəxs ona minib davam etsin.
Belə edərək, səyahət vaxtını azaltmaq olar. Sizin vəzifəniz dostlara təyinat yerinə ən qısa müddətdə necə çata biləcəklərini öyrənməkdə kömək etməkdir, nəzərə alaraq ki, velosipedi yalnız hər kəsişmədə olan xüsusi dayanacaqlarda buraxmaq olar. (əks halda velosipedsiz qala bilərlər).
Giriş verilənləri
Giriş faylının birinci sətirində iki ədəd N və M (N ≤ 150; 1 ≤ M ≤ N(N-1)/2) yazılıb. Sonra M sətir, hər biri 4 təbii ədəd - yolun təsviri: u, v, b, p. Bu o deməkdir ki, u kəsişməsindən v kəsişməsinə velosipedlə b dəqiqəyə, piyada isə p dəqiqəyə çatmaq mümkündür. Həmişə velosipedlə getmək daha qısa çəkir, yəni 1 ≤ b ≤ p ≤ 30.
Velosipedlə hərəkət edərkən sürət yolun keyfiyyətindən asılıdır.
Dostlar 1 kəsişməsindədirlər və N kəsişməsinə çatmaq istəyirlər.
Çıxış verilənləri
Təyinat yerinə çatmaq üçün lazım olan ən qısa vaxtı dəqiqələrlə tək ədəd olaraq çıxarın.