Ç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ş verilənləri

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).

Çıxış verilənləri

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.