Tianjin University Online Judge
Contests Virtual Contests Problems Submit Runs Status Rank List Forum

3256.   Traveller
Time Limit: 2.0 Seconds   Memory Limit: 65536K
Total Runs: 231   Accepted Runs: 82



The traveller Tommy is having a great time on ACM (Amazing-Chrysanthemum-Mountain) and there are N tastefully landscapes and M paths between landscapes. Now he will design a travelling route which consists of L landscapes. Since Tommy is very interested in mathematics, he expects that the total length of route is a multiple of K.

Your task is to help Tommy design such a route. If there are several solutions, choose the lexicographically smallest one. Note that any landscape can be visited more than once.

The path p[0], p[1], ... , p[n-1] is considered lexicographically smaller than the path q[0], q[1], ..., q[n-1] if there is an index i such that p[i] < q[i] and the equation p[j] = q[j] holds for all j < i.

Input

The first line of the input contains one integer T, which indicates the number of test cases.

For each test case, there are four integers N, M, K and L separated by spaces.

There are three integers S, T and V in each of the next M lines, representing a path between S and T whose length is V. All the paths are bidirectional.

The last line of each test case contains an integers P indicating the landscape site where Tommy starts (0-based indexing)

2 ≤ N, K, L ≤ 50
1 ≤ MN * (N - 1) / 2

Output

You should output a path sequence for each case separated by spaces. If there is no such a path, output -1 instead.

Sample Input

1
4 5 2 3
0 1 1
0 2 1
1 2 2
1 3 1
2 3 1
0

Sample Output

0 1 0

Author: WTommy



Source: TJU Team Selection Contest 2009 (4)
Submit   List    Runs   Forum   Statistics

Tianjin University Online Judge v1.3.0
Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz