b

Road Decoration
Add problem to Todo list
Problem code: AMR14B


SUBMITMY SUBMISSIONSALL SUBMISSIONS
Australia and New Zealand have started working on preparation for the World Cup 2015. There are N important venues (like hotels and stadiums) in the city. Out of these important venues, there is one central location where the opening and closing ceremony will be held. There is an existing network of bidirectional roads connecting these venues. The organizing committee has planned to decorate some of these roads that will be used for commuting. They have decided to choose the roads to decorate such that there is exactly one decorated path to all the venues from the central location.
New Zealand is supposed to decorate these roads and Australia has taken up the responsibility of providing transportation. Only decorated roads can be used for transportation. Australia wanted to save fuel costs, and so they wanted to choose the decorated roads to minimize the total sum of distances to all venues from the central location. However, New Zealand had their own plans to minimize decoration cost by choosing the decorated roads such that the sum of the length of the chosen roads will be minimized.
To prevent a fight breaking out between these two rivals before they even step on to the field, you have to help them by reporting if there is a solution in which the two rivals could choose the same set of roads while satisfying their respective constraints.
Input:
The first line contains the number of test cases T.
For each test first line contains N and M which are number of venues and total number of roads respectively.
Then next M lines for each case contains u, v and w - indicating that there is a bidirectional road of distance w between locations u and v.
The central location is identified with location 0.
Output:
For each test case, output the required answer on a separate line. If there is a valid plan, then print “YES”. Else, print “NO” (quotes for clarity).
Note: If any of the venues is not reachable from the central location, then print “NO”.
Constraints:
1 <= T <= 10000
1 <= N <= 20000
0 <= M <= 40000
0 <= u < N
0 <= v < N
u != v
1 <= w <= 10^9
The sum of values of N over all test cases will not be more than 1000000.
The sum of values of M over all test cases will not be more than 2000000.

Example:
Sample Input:
3
3 3
0 1 1
0 2 2
1 2 2
3 1
0 1 1
4 5
2 1 9
3 2 5
0 3 9
0 1 2
3 1 9

Sample Output:
YES
NO
NO

Explanation:
For the first case, both of them can choose the roads {0<-->1, 0<-->2}.
For the second case, venue 2 is not reachable from the central location 0.

Author:	murdocc007
Date Added:	27-12-2014
Time Limit:	6 sec
Source Limit:	50000 Bytes