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

交易市场Gxg100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
市场里面一共有n种物品，有m种交易途径，每个交易途径可以由(x,y,z)表示，意思是可以用第x种物品换成第y种物品，并且得到z元的收益（z均大于0）。最开始你只有第一种物品，请问最多可以赚取多少收益。Gxg100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
Gxg100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
时间限制：1000Gxg100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
内存限制：65536Gxg100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输入Gxg100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
第一行两个正整数n和m(n ≤ 1000，m ≤ 4000) 接下来m行，每行三个正整数x, y, z，意思是可以用第x种物品换成第y种物品，并且得到z元的收益。（1 ≤ x,y ≤ n, 1 ≤ z ≤ 100）Gxg100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
输出Gxg100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
一个整数表示最大收益，如果可以赚取无穷多的收益则输出1000000000Gxg100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
样例输入Gxg100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
3 3Gxg100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 2 2Gxg100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
2 3 3Gxg100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
1 3 4Gxg100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
样例输出Gxg100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库
5