1046：Graduation trip

sw is to going graduate, in the study in hangzhou before he'd like to have a trip. There are n cities (numbered from 1 to n), considering the actual situation, he decided to choose only m a different city travel; For convenience, the last leg of his hangzhou to a destination. sw have collected some information, he want to know in the case of minimum cost, he can choose how many kinds of schemes. Now he is to tell you the information, can you help him to solve this problem? Note: for the past, sw won't go.

The input consists of several test cases.  Each group of data is the first line of the five integers n, m, s, d, q (1 < = s, d < = n < = 100; 1 < = m < = 10; 1 < = q < = 5000) n, m, as mentioned above, s representative sw the departure city number, d number on behalf of hangzhou. Next is q lines, each line three integers, a, b, c represent the cost of the city a to city b to c (1 < = c < = 100).

Each group of data output only a line, if there is a solution, please output two integers: the minimum cost and feasible solutions. Otherwise, output -1.

4 3 1 4 4

1 2 1

2 4 2

1 3 2

3 4 1

3 3 2 3 3

1 2 1

1 3 4

2 3 4

3 2

-1

round1