Q12: Touching Shortest Paths

We're given an undirected, positively weighted graph and four nodes in the graph: a, b, c, d. Person X would like to walk from node a to b, and person Y would like to walk from node c to d. Both X and Y would like to take some shortest path between their start and end points. Design an algorithm that will determine if it is possible for X and Y to meet each other during their travels. (i.e. for X and Y to travel through a common node, while both are taking a shortest path).

Submit this problem to the judge as "Q12"

INPUT

There will be multiple test cases. The first line will contain an integer numCase equal to the number of test cases.
For each test case, the first line will contain an integer n representing the number of nodes (2 <= n <= 300). The next line contains four integers a, b, c, d, representing the start node for X, end node for X, start node for Y, and end node for Y. Nodes are numbered from 0 to n-1. The next set of lines will contain descriptions of the graph edges in the following format:

a b c

which means the there is an edge between node a and b with weight c. Nodes are numbered from 0 to n-1. Weights will be between 0 to 1000. A line with a = b = c = -1 means all the edges for this graph has be read.

OUTPUT

For each test case, output "YES" or "NO" on one line. Output "YES" if X and Y can indeed meet at a common node, "NO" if not.

Sample Input

2
6
0 4 3 5
0 1 5
1 2 6
2 3 4
3 5 9
2 5 5
2 4 5
-1 -1 -1
6
0 4 3 5
0 1 5
1 2 6
2 3 4
3 5 1
2 5 5
2 4 5
-1 -1 -1

Sample Output

YES
NO