Minimal xərcə malik maksimal axın

Giriş

Birinci sətrdə qrafın zirvələrinin sayı $n$ və kənarlarının sayı $m$ verilir ( $2 \leq n \leq 100$ 2 \leq n \leq 100, $1 \leq m \leq 1000$ 1 \leq m \leq 1000). Sonrakı $m$ sətrin hər birində dörd tam ədəd verilir: müvafiq kənarı 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 $1 0^{5}$ 10^5-dən çox deyil.

Çıxış

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

Nümunələr

Nümunə 1

Loading