BUET Inter-University Programming Contest

Problem G – Grand Wedding

 

Problem

Finally it’s the big day. The sultan is getting married. Kings, Queens and Diplomats around the world are coming to attend the Sultan’s weddings. But alas!!! Just before the grand day the royal treasury was raided. And the Sultan is now very upset about the security of his guests. As the Sultan’s minister of homeland security your job is to ensure that the whole kingdom is secured and the grand day goes on without any drift. The sultan wants that:

 

1.  Every road in the kingdom is secured by a royal guard.

 

2.  The royal guards are highly trained. When they are standing on a road intersection they can keep an eye on every road meeting at that intersection. And you have to place the guards on the intersection.

 

3.  But guards are human too!! They get bored while standing on the intersections. When they see another fellow guard on the other end of a road leaving his intersection he starts to chat with him and sometimes forget what he was supposed to do!!! The Sultan wants you to place them in such way that this incident never occurs.

 

4.  You have to ensure that conditions (1, 2, and 3) are met, and to do this you may even ask the civil works department to demolish a proper subset of the kingdom roads. The people in the civil works department are very lazy. They are so lazy that they do not want to have a list of roads and go demolish them. They just ask for a road length K and demolish all the roads with length greater or equal to K.

 

 

Now you have to secure the kingdom by conditions [1, 2, 3 and 4] and also maximize K if any road is needed to be demolished.

 

Input

The first line of input will contain an integer T  which is the number of test cases. Each of the T test cases will begin with an integer pair N and M  which are the number of intersections and number of kingdom roads respectively. The intersections are numbered from 1 to N. After that, M lines will follow. Each line contains 3 integers a, b, w  which means there is a road between intersections a and b of w length. A road between intersections (a, b) implies a road between intersections (b, a) with same length as well.

 

Output

For each test case you have to print a single integer in a separate line, the maximum K if any road is required to be demolished to secure the kingdom by conditions [1, 2, 3 and 4]. Print 0 if no road is required to be demolished. Print -1 if it is impossible to secure the kingdom by conditions [1, 2, 3 and 4].

Sample Input

Output for Sample Input

1

4 5

1 2 1

3 1 7

2 3 3

2 4 11

3 4 5

7

 

 

Problemsetter:

Shihabur Rahman Chowdhury

Special Thanks:

Md. Mahbubul Hasan