题目描述

考虑一个由以下部分组成的网络：n台计算机和m个连接。每个连接都指定了计算机向另一台计算机发送数据的速度。
Kotivalo想要从服务器下载一些数据。在现有网络连接的情况下，他能达到的最大下载速度是多少？

输入格式

第一行输入包含两个整数。n和m：计算机和连接数。计算机已编号。1,2,...,n . 计算机1是服务器和计算机n是 Kotivalo 的电脑。
此后，还有m条线描述连接关系。每条线包含三个整数。a,b,c：计算机a将数据以速度c发送到计算机b。

输出格式

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

样例数据

input

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

output

6

数据范围

1 <= n <= 500
1 <= m <= 1000
1 <= a,b <= n
1 <= c <= 10^9