题目描述

市场里面一共有 $n$ 种物品，有 $m$ 种交易途径，每个交易途径可以由 $(x,y,z)$ 表示，意思是可以用第 $x$ 种物品换成第 $y$ 种物品，并且得到 $z$ 元的收益（$z$ 均大于 $0$）。最开始你只有第一种物品，请问最多可以赚取多少收益。

输入格式

第一行两个正整数 $n$ 和 $m\ (n ≤ 1000, m ≤ 4000)$。

接下来 $m$ 行，每行三个正整数 $x, y, z$，意思是可以用第 $x$ 种物品换成第 $y$ 种物品，并且得到 $z$ 元的收益。（$1 ≤ x,y ≤ n, 1 ≤ z ≤ 100$）

输出格式

一个整数表示最大收益，如果可以赚取无穷多的收益则输出 $10^9$。

3 3
1 2 2
2 3 3
1 3 4

5