barty的智商

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

barty后宫三千,但是正宫只有一个。他的正宫为了他能好好学习,成为学霸,给他定下要求,一定要把和计算机相关的各种课程都学完。

对于每种课程,都会有几个或0个课程作为它的先修课程,只有把那些先修课程学完才能学习该课程,但是这个规定并不是特别严格。设barty的智商为T,且课程A有一门先修课程为B,根据B课程对A课程的影响,会规定一个相关系数C,如果T>=C,就是说barty足够聪明,那么就可以无视先修课程B而直接去学习A,另外一个很关键的问题就是可能存在A是B的先修课程,B是C的先修课程,C又是A的先修课程(这在实际情况中也是可能存在的),但不会有课程是它自己的先修课。

需要你计算的就是:barty的智商最低为多少的时候可以让barty学完全部课程。

Input

输入的第一行是一个整数,为数据的组数t(t<=20)。

对于每组数据,第一行为2个正整数n和m(1<=n,m<=10000),分别表示课程数和课程先修关系数,之后的m行,每行三个数ai、bi、ci,表示bi为ai的一门先修课程,且相关系数为ci(1<=ai,bi<=n,ci<=10^9)。

Output

每组数据一行,为最低需要的智商。

Sample Input

1
6 6
2 3 2
3 4 5
4 2 7
2 1 1
3 5 2
6 4 7

Sample Output

2

Source

Dshawn

Manager

Information
Solved Number147
Submit Number541
Problem Tags
binary search
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel