//Lore

AQT: Hey Imax, I've been thinking about something ...

IMAX: Hmmmm?

AQT: You ever thought about going back in time? Fixing some of your old mistakes?

IMAX: Well ... I've always thought that its good to let fate take its course .... except for that one time..... that time ruined my life.

AQT: Wanna tell me about it?

IMAX: Lets fix it instead.

This problem takes place in space-time. Space-time consists of two parts - Space and Time. Time flows continuously and can be represented by a single integer. Time flows forward, and after some waiting, any point at time and space can travel to time and space , as long as . Space, however, is more fickle. Space is represented as a connected network with nodes and edges, where each edge has an integer fuel cost to travel. Edges are eternal, and do not change as time passes. They also take no time to travel. Imaxblue wishes to counter the flow of time, and does this using special portals. Each of these portals activate at a specific time and space, and travel to a point in time in the past at the same space. These portals also cost fuel to activate.

To summarize, at any point in space-time, imaxblue has 3 actions available:

Travel along an edge in space, consuming fuel.

Travel back in time, available iff there is a portal active in his current point in space-time, consuming fuel.

Wait for time to pass in his current node, travelling FORWARD in time and staying in the same location (using 0 fuel).

Imax starts at point in space time.

Imax gives you queries: For each query, he asks: What is the least amount of fuel to get from point to point in space time?

**If it is impossible, output -1.**

#### Constraints

#### Input Format

Line 1: , the number of nodes, , the number of portals, , the number of queries, and , the maximal time.

Next lines: 3 Integers , indicating a bidirectional edge from to with weight .

Next lines: 3 Integers , indicating a portal at node from time to time with weight .

Next lines: 2 Integers , indicating a query to the point in space-time.

#### Output Format

lines, the integer answers in order of input. It is guaranteed that the answer fits into a 64 bit integer.

#### Sample Input

```
9 3 5 5
0 2 1
2 6 3
6 7 2
0 3 5
3 4 3
3 5 8
5 8 1
5 1 2
2 5 3 2
6 4 2 4
1 5 1 1
5 7
2 6
1 7
2 4
2 8
```

#### Sample Output

```
6
10
37
22
19
```

#### Sample Input 2

```
4 0 1 1
0 1 1000000000
1 2 1000000000
2 3 1000000000
1 3
```

#### Sample Output 2

`3000000000`

//lore

AQT: So, what was that bad decision you made?

IMAX: Setting that damn data structures problem on triway cup summer 2019.

## Comments