A skiing competition is taking place. There are points on the hill and trails to get from one to another. It takes seconds to get from point to (and back) on the trail. It takes the same amount of time to get back on the same trail. The competition starts from and goes to . There are competitors racing. Due to rigging of the race, the competitor will take the fastest path. Two paths are identical in rank if they take the same amount of time. A competitor may not go back to a previously visited point.

To prepare the competitors, you will provide each of them with two pieces of information, the time they will take to finish the race, and the minimum time they will spend on *one* trail.

#### Constraints

For all subtasks:

,

##### Subtask 1 [20%]

##### Subtask 2 [20%]

##### Subtask 3 [20%]

##### Subtask 4 [40%]

#### Input Specification

The first line will contain, , all space separated.

The next lines will contain three integers, and meaning a trail from to (and vice versa) will take units of time to ski.

The next lines will contain a single integer, , the designated path that the competitor will take.

#### Output Specification

lines containing two integers, the time it will take this competitor to finish the race, and the fastest time this competitor can take to get from one point to another. If there are no more paths, output `-1`

for that query.

#### Sample Input

```
5 8 1 5 4
1 2 1
1 3 2
2 3 3
3 4 2
3 5 3
2 4 1
4 5 1
1 5 5
1
2
3
4
```

#### Sample Output

```
3 1
5 1
7 1
-1
```

#### Explanation for Sample Output

The trails look like the following:

The fastest path is .

The second fastest path is .

The third fastest (slowest) path is .

A fourth path doesn't exist.

The fastest *trail* on all these paths is unit of time.

## Comments

it says paths are identical in rank if they are equal. however, do they count as multiple paths still? example: If there were paths of length 4, 6, 6 and 8, would the ranks be 1, 2, 2 and 3 or 1, 2, 2 and 4. Also, if the minimum-path is different for two paths of the same length, what do we output?

It's 1, 2, 2, 3. Take the path that minimizes the minimum trail.