You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1694 题。

题目描述

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

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

输入格式

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

$1 \leq m \leq 1000$；

$1 \leq a, b \leq n$；

$1 \leq c \leq 10^9$。