题目背景

翻译自 CSES-1694 题。

题目描述

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

Kotivalo 想从服务器下载一些数据。使用网络中的连接，他能以多大的速度进行下载？

输入格式

第一行包含两个整数 $n$ 和 $m$：分别表示计算机的数量和连接的数量。计算机编号为 $1,2,\ldots,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$