Çoxlu sayda tilləri və dövürləri olan istiqamətlənmiş qraf verilir. Hər bir til ədədlə (mənfi də ola bilər) ifadə olunmuş çəkiyə malikdir. Mənfi çəkili dövrün olmadığına zəmanət verilir.
1-ci təpədən digər bütün təpələrə ən qısa yolları tapın.
Giriş faylının ilk sətrində təpələrin n (1 ≤ n ≤ 100) sayı və tillərin m (0 ≤ m ≤ 10000) sayı verilir. Növbəti m cütlük tilləri əks etdirir: tilin başlanğıcı, tilin sonu və onun çəkisi (-100-dən 100-ə qədər tam ədədlər).
Qrafın 1-ci təpəsindən digər bütün təpələrə qədər olan ən kiçik yolları ifadə edən n ədəd verin. Əgər uyğun təpəyə gedən yol mövcud deyilsə, yolun uzunluğu yerinə 30000 ədədini verin.