Description

你是國營地獄鐵路股份有限公司的發車員(簡稱地鐵公司),地鐵公司是一家很特別的鐵路公司,很多人都想臥軌自殺,因此地鐵公司列車造成的死亡事故遠高於其他鐵路公司,作為一名地鐵公司的發車員,你不但要負責發車的工作,決定每一趟列車行經的路線與發幾輛車,還要滿足這些想臥軌的人的心願。

地鐵公司有 $n$ 個車站與 $m$ 條鐵軌,每條鐵軌連接著兩個車站且只能單向通行,地鐵公司為了省錢,地鐵公司的鐵軌都偷工減料,對於每條鐵軌,都有自己的耐久度,每開過一輛列車都會使耐久度 -1,耐久度如果小於 0,鐵軌就會崩塌,同時每條鐵軌旁都有無限個人等著臥軌被撞,為了死的體面,他們比較喜歡一個一個被撞,也就是每一班車經過一條鐵軌只能撞死一個人,作為地獄列車發車員,你要盡可能的撞死更多人。

為了更高效率的計算今天可以撞多少人,請你寫一個程式計算今天最多可以撞死多少人。

Input Format

第一行包含兩個整數 $n, m$,表示有 $n$ 個車站和 $m$ 條鐵軌。

對於每個車站,我們將其編號為 $1, 2, \ldots, n$,且車站 $1$ 是起始站,車站 $n$ 是終點站。每輛列車必須從起始站出發,開到終點站。

接下來的 $m$ 行描述了鐵軌的連接方式,每行包含三個整數 $a, b, c$,表示從 $a$ 站到 $b$ 站有一條耐久度為 $c$ 的鐵軌。

Constraints:

$1 \leq n \leq 500$

$1 \leq m \leq 1000$

$1 \leq a, b \leq n$

$1 \leq c \leq 10 ^ 9$

Output Format

請輸出一個整數,代表今天最多可以撞死多少人

Sample Input 1

4 5
1 2 3
2 4 2
1 3 4
3 4 5
4 1 3

Sample Output 1

6

Hints

隨波逐流

Subtasks

No. Testdata Range Score

TopCoder

ianwen
$\huge$

User's AC Ratio

100.0% (1/1)

Tags

Problem Source

CSES 1694

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 1000 65536 65536
5 1000 65536 65536
6 1000 65536 65536
7 1000 65536 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536
11 1000 65536 65536
12 1000 65536 65536
13 1000 65536 65536
14 1000 65536 65536
15 1000 65536 65536