網路流

題目敘述

為了加速用戶從伺服器端下載資料的傳輸速度，我們利用許多的中繼節點來增加頻寬。網路由 $N$ 個節點， $M$ 條雙向的網路線所組成，每條線上有一個整數 $c$ ，代表那條線的傳輸速度上限。 請問從 $1$ 號節點到 $N$ 號節點的傳輸速度上限是多少？

輸入說明

第一行會有兩個數字 $N, M$ 代表有 $N$ 個節點， $M$ 條網路線。
接下來會有 $M$ 行，每一行會包含三個整數 $u$, $v$, $c$，代表有一條連接 $u, v$ 的網路線，他的傳輸速度上限是 $c$。
其中 $1\leq u,v \le N \leq 300$ , $0\le M\le 1,000$ , $0\le c\le 10^6$。

輸出說明

請輸出從 $1$ 號節點到 $N$ 號節點的傳輸速度上限是多少？

範例輸入

3 3
1 2 7
2 3 5
1 3 2

範例輸出

7

配分方法

• 20% $1 \leq N \leq 30$, $1 \leq M \leq 100$
• 100% $1 \leq N \leq 300$, $1 \leq M \leq 1,000$

Hints

備註

Judge Setting