Help John!

Time Limit: 1 Second    Memory Limit: 32768 KB

John is 7 years old and he lives in Faegfalch, which is a very dangerous city, so John must go to school according to the path his mother told him. This way isn't the fastest way from John's home to school. John is a very lazy boy and he doesn't like walking, so he is searching for the fastest way from home to school. He only has to make sure, that his mother can not see from her flat window that he is going on another way (he must pass the first crossroad where mother told him to go across, and never walk back home unless he comes back from school).

Input

First line of input includes t (1<=t<=77) - the number of test cases.

First line of every test includes n (1<=n<=1 000) - the number of crossroads in Faegfalch and m (1<=m<=30 000) - the number of roads. In next m lines there are descriptions of roads. Every road description includes three numbers: a, b (1<=a, b<=n) - crossroads, where the road starts and ends and c (1<=c<=1 000) - the time needed to walk by this street (John can't walk faster, because if he did it, he would be cought by Faegnad (football team) fans and he can't go slower, because he doesn't want to be late and he wants to talk with his friends and make some homework before lessons start). In next line there is an integer k (1<=k<=m) - the number of crossroads, which his mother told him to meet. Next line includes k crossroads which he has to meet.

The boy's home is always at location 1 and the school positions at location n. All the paths are bidirectional.

Output

Output has one line for every test, which include word "TEST" and then the order number. Print the character "Y" if John can go to his school from home, and the time needs to go to school by roads which his mother told him to go, subtracts the minimal time which he needs to walk to school that can not be seen by his mother. Output only an "N" if there is no way to his school.

Sample Input

2
6 10
1 2 2
1 3 2
1 6 1
2 6 4
2 3 3
2 4 1
3 4 5
4 5 1
4 6 3
5 6 2
6
1 2 3 4 5 6
3 1
1 2 1
3 
1 2 3

Sample Output

TEST 1 Y 7
TEST 2 N
Submit

Source: 3MG_Contest