链接: https://cses.fi/problemset/task/1694

板块: Graph Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

考虑一个由 $n$ 台计算机和 $m$ 个连接组成的网络。每个连接指定了一台计算机能向另一台计算机发送数据的速度。

Kotivalo 想从一台服务器下载一些数据。利用网络中的连接，他能达到的最大下载速度是多少？

输入

第一行输入包含两个整数 $n$ 和 $m$：计算机数量和连接数。计算机编号为 $1,2,\dots,n$。计算机 $1$ 是服务器，计算机 $n$ 是 Kotivalo 的计算机。

之后有 $m$ 行描述连接。每行包含三个整数 $a$、$b$ 和 $c$：计算机 $a$ 能以速度 $c$ 向计算机 $b$ 发送数据。

输出

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

数据范围

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

样例输入

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

样例输出

6