CHRIS - On the Way to Find Chris

no tags 

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:

  • If Yashiro's home is nearer than Shermie's, she will go to Yashiro's home first, if she doesn't find Chris, she will then go to Shermie's, and vice versa.
  • The map of the city is strange. Each of the houses is assigned to a unique number in the range[1,n], where n is the number of houses. Between some pairs of houses there are some roads. There exists one and only one path from any house to any other house. She will go along the only path between the two houses.

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 ≤ 109).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
Warning: large Input/Output data, be careful with certain languages

hide comments
Aditya Muraletharan: 2013-01-03 07:04:02

Thank you Buda IM. You helped me save a lot of time:)

Re( by Buda IM ) : even my first submission was correct, but I had to spend hours removing ghostly sigsegv :)

Last edit: 2013-01-03 23:35:19
Buda IM (retired): 2012-12-31 15:21:33

you can get sigsegv due to stack overflow


Added by:Fudan University Problem Setters
Date:2007-04-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO
Resource:Chinese National Olympiad in Informatics 2003,Day 2; translated by Blue Mary