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

Ən böyük axın A

Ən böyük axın A

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

n təpə nöqtəsi olan dövürsüz və sox sayda tilləri olan istiqamətlənməmiş qraf verilir (təpə nöqtələri 1-dən n-ə qədər nömrələnmişdir). Hər bir tilin ötürücülük qabiliyyəti məlumdur. 1 təpəsindən n təpəsinə ən böyük axını təyin edin. Hər bir tilldə axın istənilən istiqamətdə ola bilər.

Giriş verilənləri

Giriş verilənləri qrafdakı təpələr və tillərin sayını ifadə edən iki nk~(2 \le n \le 100, 0 \le k \le n \cdot (n - 1) / 2) ədədlərini ehtiva edir. Daha sonra hər birində tilin birləşdirdiyi təpələrin nömrələrini və tilin ötürücülük qabiliyyətini ifadə edən üç a, b, c~(1 \le a, b \le n, 1 \le c \le 10^9) ədədlərini ehtiva edən k sətir verilir.

Çıxış verilənləri

1 təpəsindən n təpəsinə ən böyük axının qiymətini təyin edin.

Nümunə

Giriş verilənləri #1
5 7
1 2 2
2 5 5
1 3 6
3 4 2
4 5 1
3 2 3
2 4 1
Çıxış verilənləri #1
6
Mənbə III International Summer School Programming in Sevastopol 2012