Optimal axın böyüklüyü 1
Verilmiş qrafda n təpə və m kənar mövcuddur. Təpə 1 başlanğıc, təpə n isə son nöqtə kimi müəyyən edilib. Hər bir kənara müəyyən bir qiymət təyin olunub.
Bu şəbəkədə 1 vahidlikdə optimal axını tapın, yəni ən az qiymətə malik olan 1 vahidlikdə axını müəyyən edin. Kənarların qiymətləri mənfi ola bilər, lakin qrafda mənfi çəkili dövrələrin olmadığı məlumdur. Keçiricilik qabiliyyətləri sizə verilməyib, lakin onların 1-dən az olmadığı məlumdur.
Giriş verilənləri
Birinci sətirdə n və m (2 ≤ n ≤ 1000, 0 ≤ m ≤ 10000) ədədləri verilir. Sonra m sətir var, hər birində üç tam ədəd x, y, p - x-dən y-yə olan kənarın qiyməti p-dir (1 ≤ x, y ≤ n, -1000 ≤ p ≤ 1000). Qrafda döngələr və çoxlu kənarlar ola bilər.
Çıxış verilənləri
Bir tam ədəd çıxarın - 1 vahidlikdə optimal axının qiyməti. Əgər şəbəkədə 1 vahidlikdə axın yoxdursa, NO çıxarın.