Do you know the famous game THE KING OF FIGHTERS? If the answer is yes, I'm sure you know THE THREE BLACK GROUP: Chris, Shermie and Yashiro. Today Chris is invited to one of his friends' home to play THE KING OF FIGHTERS. Blue Mary is now at Chris' home, she knows where Shermie's and Yashiro's home is, but she doesn't know where Chris actually is. So she decides that:

Unfortunately, you don't know where Chris' home actually is, and the same as Yashiro's and Shermie's. Now you are interesting in the maximum time from the time when Blue Mary starts from Chris' home to the time when Blue Mary finds Chris in the worst case.

Input

The number of test cases T is given in the very first line. T blocks follow.

For each test case, the first line contains 2 space-separated integers N (3 ≤ N ≤ 200000) and M, which denotes the number of houses and the number of roads in the city. M lines follow, each contains 3 space-separated integers x, y, z (1 ≤ x, y ≤ n, 1 ≤ z ≤ 10⁹).It tells us there exist a road between house number x and house number y, and to go from x to y or from y to x along this road will take z minutes. No two roads are repeated.

Output

For each test case you should output a single line, which contains a single integer - the maximum time measured in minutes.

Example

Input:
1
4 3
1 2 1
2 3 1
3 4 1

Output
4