//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 it's good to let fate take its course … except for that one time… that time ruined my life.

AQT: Wanna tell me about it?

IMAX: Let's 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 ~T~ and space ~S~ can travel to time ~U~ and space ~S~, as long as ~T < U~. Space, however, is more fickle. Space is represented as a connected network with ~N~ nodes and ~N-1~ 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:

1. Travel along an edge in space, consuming ~w_i~ fuel.

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

3. 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 ~(T, 0)~ in space-time.

Imax gives you ~Q~ queries. For each query, he asks: What is the least amount of fuel to get from point ~(T, 0)~ to point ~(S, P)~ in space-time? ~(1 \le S \le T, 0 \le P < N)~

If it is impossible, output -1.

Constraints

~0 \le Q, N, M \le 10^5~

~0 \le X, Y, P < N~

~0 \le S, E \le T \le 200\,000~

~0 \le W \le 10^7~

Input Specification

Line 1: ~N~, the number of nodes, ~M~, the number of portals, ~Q~, the number of queries, and ~T~, the maximal time.

Next ~N-1~ lines: 3 integers ~X, Y, W~, indicating a bidirectional edge from ~X~ to ~Y~ with weight ~W~.

Next ~M~ lines: 3 integers ~X, S, E, W~, indicating a portal at node ~X~ from time ~S~ to time ~E~ ~(S > E)~ with weight ~W~.

Next ~Q~ lines: 2 integers ~S, P~, indicating a query to the point ~(S, P)~ in space-time.

Output Specification

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

Sample Input 1

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 1

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.