İki ən qısa yol
Dünən Vasya və Petya ciddi mübahisə etdilər və bu gün məktəbə gedərkən bir-birlərini yollarında görmək istəmirlər. Problem ondadır ki, onlar eyni binada yaşayırlar, məktəbə eyni vaxtda çıxırlar və ən qısa yolla eyni sürətlə gedirlər. Uşaqlar öz vərdişlərini dəyişmək istəmirlər və eyni yolla getməmək üçün iki fərqli ən qısa yol tapmaq istəyirlər. Lakin onlar yol şəbəkəsinin qovşaqlarında görüşə bilərlər, çünki qısa müddətli görüş onları qıcıqlandırmır.
Uşaqlar sizdən onlara kömək etməyi xahiş edirlər. Bunun üçün onlar qovşaqları 1-dən N-ə qədər nömrələyiblər. Onların evi və məktəbi müvafiq olaraq 1 və N nömrəli qovşaqlarda yerləşir. Qovşaq cütləri arasında bir yoldan çox yol ola bilməz.
Giriş verilənləri
Birinci sətir N və M (2 ≤ N ≤ 400) tam ədədlərini ehtiva edir, burada M — Petya və Vasya tərəfindən qeyd olunan yolların sayıdır. Növbəti M sətirin hər biri üç tam ədəd ehtiva edir: X, Y və L (1 ≤ X, Y ≤ N, 1 ≤ L ≤ 10000), burada X və Y — yol ilə birləşdirilən qovşaqların nömrələri və yolun uzunluğudur.
Çıxış verilənləri
Birinci sətirdə birinci ən qısa yolun qovşaq nömrələrini göstərin. İkinci sətirdə — ikinci yolun. Əgər həll mövcud deyilsə, "No solution" (tırnaq işarələri olmadan) yazın.