Contests | Virtual Contests | Problems | Submit | Runs Status | Rank List | Forum |

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*.### Input

The first line of the input contains one integer *T*, which indicates the number of test cases.### 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

### Sample Output

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*.

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 ≤ *M* ≤ *N* * (*N* - 1) / 2

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

0 1 0

**Author:** WTommy

Maintance:Fxz. Developer: SuperHacker, G.D.Retop, Fxz