Problem D: 考古小分队
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：73
Solved：38
Description
考古小分队在不同的区域工作，所经受的气温是不同的，这一年小分队要在以下的行程图完成一项考古任务。行程图是1至n个区域的有向图，数值标示了区域内的温度值。考古小分队在出发前，请你帮助计算出从区域1开始到区域n的最大的温度和是多少？(注意，此题有负值边。)
输入数据第一行表示图的顶点数 n和边数 m。接下来 m 行，每行三个整数 u、v 和 t，表示 u 区域到v 区域工作时的温度值 t。输出从 1号区域开始到 n号区域结束的考古小分队可能经受的最大温度和值为多少。下图示例数据为样例输入数据。图示从1至6最大值路径为 1−4−2−5−6，最大值为15.
Input
输入数据第一行表示图的顶点数 n和边数 m。接下来 m 行，每行三个正整数 u、v 和 t，表示 u 区域到v 区域工作时的温度值 t。
Output
输出从 1号区域开始到 n号区域结束的考古小分队可能经受的最大温度和值为多少。
Sample Input Copy
6 10
1 2 3
1 4 5
2 3 4
2 5 7
2 6 2
3 6 -2
4 2 2
4 5 6
5 3 -1
5 6 1
Sample Output Copy
15
HINT
2=<n<=30 ; 此题边值 t范围 -99 =<t<=99 (有负值边)