The first line of the test data will start with an integer T representing the T test cases, then, T cases will follow, each of the cases starts with three integers, V E and M, denoting, respectively, the number of the rooms on the cave, the numbers of tunnels in the cave and the number of hammers Charlie will carry, the next E lines will contain six integers, denoting, respectively, the origin room i, the destiny room j, opening time x, collapse time y, distance z, and time t.

Output

You must output the string "Scenario #i: " where i is the number of test case you're analyzing, followed by the minimum time and the minimum distance associated to it, if Charlie isn't able to arrive to the V-1 room, output -1.

Example

Input:
4
6 6 2
0 1 1 18 3 3
0 2 1 12 4 4
0 4 1 3 5 5
2 3 1 8 2 2
3 4 1 5 3 3
4 5 5 20 1 1
6 6 1
0 1 1 18 3 3
0 2 1 12 4 4
0 4 1 3 5 5
2 3 1 8 2 2
3 4 1 5 3 3
4 5 5 20 1 1
6 6 0
0 1 1 18 3 3
0 2 1 12 4 4
0 4 1 3 5 5
2 3 1 8 2 2
3 4 8 25 3 3
4 5 5 20 1 1
3 3 0
0 1 0 5 4 4
1 2 0 5 2 2
0 2 0 5 6 6

Output:
Scenario #1: 6 6
Scenario #2: 7 6
Scenario #3: 12 10
Scenario #4: -1

Constraints

1 <= T <= 10

Small input: (20%)

2 <= V <= 10

1 <= E <= 30

M = 0

Medium input: (30%)

2 <= V <= 100

1 <= E <= 1,000

M = 0

Large input: (50%)

2 <= V <= 100

1 <= E <= 1,000

0 <= M <= 50

It is guaranteed that the distance of the tunnels won't never exceed 10.

1 <= opening and collapse times <= 100,000

Clarifications: You start with time 0. It will be always true that the time x will be lesser or equal than time y. While passing through a tunnel from room i to room j, if the tunnel collapses while you're inside, you can use a hammer to break through, otherwise that path is impossible to take.