最长滑雪道

Grade 100 Open Time Wednesday, 17 June 2020, 9:25 PM
Discount 0.8 Time Discount Wednesday, 17 June 2020, 9:25 PM
Allow late Yes Close Time Wednesday, 17 June 2020, 9:25 PM
Input file skiing.in Output file skiing.out

【题目描述】最长滑雪道(skiing)2017 ACM-ICPC 亚洲区(乌鲁木齐赛区)网络赛

山顶雪场有m条滑雪道和n个标志旗,每两个标志旗之间的路径长度不同,一条可用的滑雪道将从一面标志旗开始,穿过几面标志旗,到某一个标志旗结束。

每条滑雪道都严格遵循高度降低的原则,并且起点严格高于终点,小光想找出最长的滑雪道。

【输入格式】

第一行为一个整数T,表示有T组数据。

每组数据第一行有两个整数n和m(0<n≤10 000,0<m≤100 000),表示滑雪道数和标志旗数。随后m行,每行3个整数S,T,L,表示滑雪道的起点,终点和长度。

【输出格式】

每组数据输出一个整数,表示最长的滑雪道。

【输入样例】

1

5 4

1 3 3

2 3 4

3 4 1

3 5 2

【输出样例】

6