Download Speed

题目描述

考虑一个由 $n$ 台计算机和 $m$ 条连接组成的网络。每条连接指定了一台计算机向另一台计算机发送数据的速度。 Kotivalo 想从服务器下载一些数据。他使用网络中的连接，最大可以以多大的速度下载这些数据？

输入格式

第一行输入包含两个整数 $n$ 和 $m$：计算机的数量和连接的数量。计算机编号为 1,2,$\dots$,n。计算机 1 是服务器，计算机 n 是 Kotivalo 的计算机。 接下来有 $m$ 行描述连接。每行有三个整数 $a$, $b$ 和 $c$：计算机 $a$ 可以以速度 $c$ 向计算机 $b$ 发送数据。

输出格式

输出一个整数：Kotivalo 可以下载数据的最大速度。

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

6

提示

$1 \le n \le 500$ $1 \le m \le 1000$ $1 \le a,b \le n$ $1 \le c \le 10^9$

标签: CSES1694|图论

来源

CSES1694|图论