eolymp
bolt
Try our new interface for solving problems
Məsələlər

Ford-Bellman

Ford-Bellman

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Ç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 (1n100) sayı və tillərin m (0m10000) 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.

Nümunə

Giriş verilənləri #1
4 5
1 2 10
2 3 10
1 3 100
3 1 -10
2 3 1
Çıxış verilənləri #1
0 10 11 30000