On 5.1 this year, the 41st World Exposition was held in Shanghai. In order to visit the World Exposition, reason flied to Shanghai. When he arrived at the airport, he was very excited. Because this was the first time he went to Shanghai. After the opening of the World Exposition, he wanted to walk around the city. Shanghai was beautiful, he went to some of attractions. Such as Nanjing Road, Oriental Pearl and Bund, etc. He went east and west, suddenly he found himself lost his way. He asked for your help.
There are N stops and M roads, reason was at stop S, he wanted to go to stop T. Reason was a lazy boy, he want to go to the stop T as short as possible. At the same time, reason has a habit, he always likes to walk to the stop T in K roads, and K is a multiple of X.
The input consists of several test cases. The first line is the number of test cases.
For each test case, the first line is the integer n and m, means there are N stops and M path, 1 ≤ N ≤ 100, 1 ≤ M ≤10000.
Then M lines, three number u, v, w. means there is a directed road from u to v, w is the length of the road. 0 ≤ u, v ≤ n, 0 ≤ w ≤ 230.
Last line contains three number: S, T and X. 0 ≤ S, T ≤ n, 1 ≤ X ≤ 10.
There is a blank line between each case.
For each test case, output the total distance reason likes to walk from S stop to T stop. If there is no such path, output “No Answer!”