题目描述

市场里面一共有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）$

输出

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

样例

3 3
1 2 2
2 3 3
1 3 4

5