Maksimal axın 2

Sizə istiqamətli qraf G verilib. Hər bir kənarın müəyyən bir keçirmə qabiliyyəti mövcuddur. 1 və n zirvələri arasında maksimum axını tapın.

Giriş verilənləri

Giriş faylının ilk sətiri qrafın zirvə və kənar sayını - n və m (2 ≤ n ≤ 500, 1 ≤ m ≤ 10000) ehtiva edir. Sonrakı sətirlər kənarları təsvir edir. Hər bir kənar üç ədəd ilə verilir: kənarın başlanğıc zirvəsi, kənarın son zirvəsi və kənarın keçirmə qabiliyyəti. Keçirmə qabiliyyətləri 10^9-u keçmir.

Çıxış verilənləri

1 və n zirvələri arasında maksimum axının ölçüsünü çıxarın.

Nümunələr