Charlie is picking some precious stones in a cave, this cave is known worldwide by the stones in it, however, this cave is very delicate and the minimum movement causes an instant collapse, Charlie knows the times that the tunnels will be free (as the instant collapses can free some tunnels) or covered by a pile of stones.

 

In his backpack, Charlie has some magical hammers that he carries for emergency, in some expeditions he won't have these hammers, but in others he will. The hammer causes an instant opening of any pile of stones blocking his way.

 

It is also known that Charlie travels some distance d in a time t from room i to room j, and the tunnel connecting them will be free from time x to time y. Charlie can return whenever he wants, so, traveling from room j to room i will be symmetric.

 

Charlie doesn't have infinite hammers, so, when he use one, the hammer will break, making it useless.

 

In addition, if Charlie knows that the tunnel will open in a time X, he can choose to stay until the path opens or use a magical hammer to go through the tunnel.

 

Given that information, your task is to find the minimum time with the minimum distance that Charlie can go from the entrance (0) to the center of the cave (V-1)

 

INPUT:

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.

 

INPUT	OUTPUT
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	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.