Minimum dəyəri olan maksimal axın

Verilmiş istiqamətli qrafda hər bir kənarın ötürmə qabiliyyəti və dəyəri mövcuddur.

1 nömrəli zirvədən n nömrəli zirvəyə minimal dəyərli maksimal axını tapın.

Giriş verilənləri

Giriş faylının ilk sətiri qrafın zirvələrinin sayı n və kənarlarının sayı m -ni ehtiva edir (2 ≤ n ≤ 100, 1 ≤ m ≤ 1000). Növbəti m sətirin hər biri dörd tam ədəd ehtiva edir: qrafın müvafiq kənarını birləşdirən zirvələrin nömrələri, onun ötürmə qabiliyyəti və dəyəri. Ötürmə qabiliyyəti və dəyəri 10^5-dən çox deyil.

Çıxış verilənləri

Çıxış faylına bir ədəd yazın - 1 nömrəli zirvədən n nömrəli zirvəyə minimal dəyərli maksimal axının qiyməti. Cavab 2^63-1-dən çox deyil. Qrafda mənfi dəyərli dövrlərin olmadığı təmin edilir.

Nümunələr