ADA Classes - November 6


In one country, there aren cities, numbered 1 to n. A civil engineer has to build public roads that connect all the cities together, i.e. it must be possible to travel from all cities to any other cities, maybe going through multiple cities. His team has surveyed several routes (candidate road between any two cities). Each route is a bidirectional connection between two cities. He can build a bidirectional road on the surveyed route for a specific cost (The shorter the route is the cheaper the road).

This engineer has never planned a road system in advance. He would just pick one of the routes based on his preference, and build a road until all the cities are connected.

Right now this engineer is going to build a road from the city p to the city q. With pressure from the government to reduce the cost, he asks you to write a program to decide, if he should build this road or not. Your program should say yes if the building of this road guaranteed that it can be part of the shortest road system that connects all cities together. Otherwise, your program should say no.


First line is a number of test cases t (t10).

Each test case starts with a line contains 4 integers n, m, p and q. Here n (2n10000) is the number of cities in this road system, m (1m20000) is the number of surveyed routes, p and q (1pn, 1qn) indicate the route between two cities, that the engineer asks if he can build a road or not.

Then, the each of the following m lines contains 3 numbers u, v and w (1un, 1vn, 1w400000) indicates that there are the bidirectional route of length w between u and v. The length of each road in the current system is unique. And, there is only one possible road between two cities. The input guarantees that at least one road system has a route between any two cities. All numbers are integer.


For each test case, display YES if the engineer can build a road p - q as part of the shortest road system. Otherwise, print NO.

Time limit 1 second
Memory limit 128 MiB
Input example #1
2 1 1 2
1 2 4
3 3 2 3
1 2 1
1 3 2
2 3 3
4 5 3 4
1 2 1
1 3 3
3 4 2
1 4 4
4 2 5
Output example #1
Source 2013 ACM ICPC Asia Thailand National programming Contest