Petya loves volleyball very much. One day he was running late for a volleyball match. Petya hasn't bought his own car yet, that's why he had to take a taxi. The city has *n* junctions, some of which are connected by two-way roads. The length of each road is defined by some positive integer number of meters; the roads can have different lengths.

Initially each junction has exactly one taxi standing there. The taxi driver from the *i*-th junction agrees to drive Petya (perhaps through several intermediate junctions) to some other junction if the travel distance is not more than *t*<sub class="lower-index">*i*</sub> meters. Also, the cost of the ride doesn't depend on the distance and is equal to *c*<sub class="lower-index">*i*</sub> bourles. Taxis can't stop in the middle of a road. Each taxi can be used no more than once. Petya can catch taxi only in the junction, where it stands initially.

At the moment Petya is located on the junction *x* and the volleyball stadium is on the junction *y*. Determine the minimum amount of money Petya will need to drive to the stadium.
The first line contains two integers *n* and *m* (1 ≤ *n* ≤ 1000, 0 ≤ *m* ≤ 1000). They are the number of junctions and roads in the city correspondingly. The junctions are numbered from 1 to *n*, inclusive. The next line contains two integers *x* and *y* (1 ≤ *x*, *y* ≤ *n*). They are the numbers of the initial and final junctions correspondingly. Next *m* lines contain the roads' description. Each road is described by a group of three integers *u*<sub class="lower-index">*i*</sub>, *v*<sub class="lower-index">*i*</sub>, *w*<sub class="lower-index">*i*</sub> (1 ≤ *u*<sub class="lower-index">*i*</sub>, *v*<sub class="lower-index">*i*</sub> ≤ *n*, 1 ≤ *w*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>) — they are the numbers of the junctions connected by the road and the length of the road, correspondingly. The next *n* lines contain *n* pairs of integers *t*<sub class="lower-index">*i*</sub> and *c*<sub class="lower-index">*i*</sub> (1 ≤ *t*<sub class="lower-index">*i*</sub>, *c*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">9</sup>), which describe the taxi driver that waits at the *i*-th junction — the maximum distance he can drive and the drive's cost. The road can't connect the junction with itself, but between a pair of junctions there can be more than one road. All consecutive numbers in each line are separated by exactly one space character.
An optimal way — ride from the junction 1 to 2 (via junction 4), then from 2 to 3. It costs 7+2=9 bourles.
4 4
1 3
1 2 3
1 4 1
2 4 1
2 3 5
2 7
7 2
1 2
7 7
9
3 3
1 3
1 2 2
1 3 3
3 2 1
2 7
2 7
3 6
14
3 1
1 3
1 2 2
2 7
2 7
3 6
-1
3 2
3 3
1 2 2
1 3 3
2 7
2 7
3 7
0
2 2
1 2
1 2 3
1 2 2
2 7
3 2
7
1 0
1 1
74 47
0
5 5
1 3
1 3 3
5 1 6
4 3 8
1 3 3
5 2 4
1 2
4 1
2 5
5 2
1 2
-1
7 4
3 4
6 2 7
6 1 4
4 3 5
3 6 4
1 6
7 3
3 6
6 5
3 7
4 4
1 4
-1
5 5
4 5
1 4 8
4 2 4
4 1 3
3 1 9
4 5 4
2 7
2 7
5 1
6 3
3 2
3
5 5
5 4
2 4 10
2 4 7
3 1 7
2 4 2
5 3 9
6 17
2 4
3 12
7 18
2 5
-1
4 7
3 4
2 3 5
3 2 9
4 1 9
3 2 1
3 1 2
2 3 6
1 2 8
2 2
5 3
2 1
1 5
-1
7 14
7 5
1 3 15
2 1 10
1 3 5
2 4 9
5 4 19
1 3 11
5 1 1
2 4 5
2 3 11
3 2 10
3 4 18
5 1 18
6 2 5
5 6 2
3 6
6 7
9 1
3 6
1 1
9 4
9 8
-1
7 15
5 5
3 4 6
7 4 3
7 2 8
2 5 2
7 2 8
5 2 9
3 1 7
1 2 4
7 1 8
7 5 7
2 4 2
4 3 9
7 4 2
5 4 8
7 2 8
15 4
18 18
6 8
16 5
11 1
5 3
18 4
0
8 20
8 4
6 3 1
3 4 4
5 2 2
3 6 3
5 8 7
6 2 7
8 6 4
6 4 5
4 2 5
5 3 3
5 7 3
8 1 6
2 4 3
6 8 5
1 8 6
8 2 7
8 2 3
1 6 7
8 7 3
6 3 6
2 2
5 9
1 9
4 7
1 8
4 8
9 7
9 3
3
8 20
8 2
1 7 5
3 2 3
2 7 6
6 5 6
4 8 5
7 8 4
1 6 2
7 4 3
4 3 1
6 7 5
4 2 4
2 8 7
6 2 2
2 3 4
3 7 3
7 8 4
5 4 2
7 1 1
5 7 3
4 3 7
4 4
2 7
3 5
3 1
3 5
1 5
11 4
10 5
5
9 20
5 1
8 9 3
1 8 6
5 6 3
2 1 4
7 1 6
1 4 4
3 2 4
5 6 4
3 9 6
6 2 3
9 1 7
1 7 1
1 3 3
8 4 7
7 1 7
6 9 3
5 8 3
9 4 5
6 9 1
6 2 6
1 7
1 3
6 1
1 2
6 1
2 2
4 7
4 5
4 1
-1
10 21
9 5
5 2 6
1 9 7
6 2 7
8 10 2
7 2 1
6 9 6
10 9 4
2 10 2
10 8 4
10 1 7
9 1 7
1 8 5
10 9 7
7 5 3
2 10 6
4 7 3
10 5 6
5 10 4
6 9 2
2 3 6
1 9 3
10 6
7 12
13 3
17 4
18 17
1 9
16 16
12 13
1 10
6 15
-1
14 20
7 2
12 2 17
13 3 8
6 8 3
14 4 16
13 5 17
7 14 7
11 10 6
12 4 16
6 11 7
2 13 12
13 2 18
2 10 12
13 12 1
12 5 4
9 4 16
7 6 7
2 3 15
4 14 1
13 5 3
10 9 3
4 6
4 5
5 3
2 6
2 4
1 2
4 7
2 2
6 1
1 1
6 5
7 7
3 4
2 6
-1
15 29
6 6
7 12 7
11 3 7
4 5 18
13 9 18
3 8 12
6 1 7
4 1 4
12 5 18
10 8 15
2 10 1
9 7 11
2 4 10
2 14 3
15 12 14
1 13 8
11 4 1
15 11 2
1 5 9
5 2 5
9 10 5
15 2 17
11 5 1
14 15 14
10 1 16
15 9 2
13 15 6
13 5 1
7 12 6
12 5 13
8 26
35 17
16 14
12 13
21 1
31 9
7 24
11 31
29 5
16 22
29 7
30 20
36 3
26 22
37 6
0
5 0
2 4
1 2
6 9
4 585
6 9
7 4
-1
5 8
1 3
1 2 1
1 3 3
1 5 1
1 4 2
5 4 3
3 5 2
2 3 8
1 3 2
2 7
10 3
4 7
2 1
1 1
7
5 7
1 3
1 2 1
1 3 3
1 5 1
1 4 2
5 4 3
3 5 2
2 3 8
2 7
10 3
4 7
2 1
1 1
10
7 5
6 7
1 3 1000000000
2 7 999999999
5 7 123456789
1 5 148879589
5 4 1000000000
1000000000 1000000000
1000000000 1000000000
999999999 145785965
1000000000 1000000000
1000000000 1
123456789 123568591
1000000000 1000000000
-1
7 8
6 7
1 3 1000000000
1 6 1000000000
1 2 1000000000
6 2 1000000000
2 5 1000000000
5 7 1000000000
4 7 1
3 4 1000000000
1000000000 100000000
999999999 1
1000000000 10000000
1000000000 10000000
1000000000 128
1000000000 10000000
1000000000 1000000000
130000000
7 8
6 7
1 3 1000000000
1 6 1000000000
1 2 1000000000
6 2 1000000000
2 5 1000000000
5 7 1000000000
4 7 1
3 4 999999999
1000000000 100000000
999999999 1
999999999 10000000
1000000000 10000000
1000000000 128
1000000000 10000000
1000000000 1000000000
130000000
7 8
1 7
1 3 1000000000
1 6 1000000000
1 2 1000000000
6 2 1000000000
2 5 1000000000
5 7 1000000000
4 7 1
3 4 999999999
1000000000 100000000
999999999 1
999999999 10000000
1000000000 10000000
1000000000 128
1000000000 10000000
1000000000 1000000000
120000000
2 1
1 2
1 2 1
1 999999998
1 999999998
999999998
3 3
1 3
2 1 1
1 2 1000000000
1 2 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
-1
3 3
1 2
2 1 1
1 2 1000000000
1 2 1000000000
10000000 1000000000
10000000 1000000000
10000000 1000000000
1000000000
3 3
1 2
2 1 1000000000
1 2 1000000000
1 2 1000000000
10000000 1000000000
10000000 1000000000
10000000 1000000000
-1
from heapq import *


def read_integers():
    return map(int, input().split())


inf = 1e13
n, m = read_integers()
x, y = read_integers()
roads = [[] for i in range(n + 1)]

for j in range(m):
    u, v, w = read_integers()
    roads[u].append((v, w))
    roads[v].append((u, w))

drivers = [(0, 0)] + [tuple(read_integers()) for k in range(n)]
C, T = {x: 0}, {x: 0}
heap = [(0, x, 0, 1)]

while heap:
    cost, junction, time, query = heappop(heap)

    if junction == y:
        exit(print(cost))
    
    driver_time, driver_cost = drivers[junction]

    if time < driver_time and query:
        heappush(heap, (cost + driver_cost, junction, driver_time, 0))
    
    for neighbor, road_length in roads[junction]:
        new_time = time - road_length
        if new_time >= 0:
            if cost < C.get(neighbor, inf) or new_time > T.get(neighbor, -1):
                C[neighbor], T[neighbor] = cost, new_time
                heappush(heap, (cost, neighbor, new_time, 1))

print(-1)# 1698324509.0968862