CF95C.Volleyball

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__i meters. Also, the cost of the ride doesn't depend on the distance and is equal to c__i 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.

佩佳非常喜欢排球。有一天，他赶着去参加一场排球比赛，却迟到了。佩佳还没有买自己的汽车，因此他不得不乘坐出租车。这座城市共有 $n$ 个路口，其中一些路口由双向道路连接。每条道路的长度为某个正整数（单位：米）；不同道路的长度可以不同。

最初，每个路口恰好停有一辆出租车。第 $i$ 个路口的出租车司机同意载佩佳（可能经过若干中间路口）前往其他某个路口，前提是总行驶距离不超过 $t_i$ 米。此外，乘车费用与行驶距离无关，恒为 $c_i$ 博尔（bourles）。出租车不能在道路中途停车。每辆出租车最多只能被使用一次。佩佳只能在出租车初始停放的路口上车。

当前佩佳位于路口 $x$，而排球馆位于路口 $y$。请确定佩佳抵达排球馆所需的最少花费（单位：博尔）。

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__i, v__i, w__i (1 ≤ u__i, v__i ≤ n, 1 ≤ w__i ≤ 109) — 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__i and c__i (1 ≤ t__i, c__i ≤ 109), 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.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 1000$，$0 \leq m \leq 1000$），分别表示城市中路口的数量和道路的数量。路口编号为 $1$ 到 $n$（含端点）。
下一行包含两个整数 $x$ 和 $y$（$1 \leq x, y \leq n$），分别表示起点路口和终点路口的编号。
接下来的 $m$ 行描述道路信息。每条道路由三个整数 $u_i$、$v_i$、$w_i$（$1 \leq u_i, v_i \leq n$，$1 \leq w_i \leq 10^9$）描述——它们分别表示该道路所连接的两个路口编号以及该道路的长度。
接下来的 $n$ 行每行包含一对整数 $t_i$ 和 $c_i$（$1 \leq t_i, c_i \leq 10^9$），描述位于第 $i$ 个路口的出租车司机：$t_i$ 表示该司机最多可行驶的距离，$c_i$ 表示乘坐该司机车辆的费用。
道路不能连接同一个路口（即不允许自环），但任意两个路口之间可能存在多条道路。
每行中所有相邻数字之间恰好用一个空格分隔。

If taxis can't drive Petya to the destination point, print "-1" (without the quotes). Otherwise, print the drive's minimum cost.

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.

如果出租车无法将佩蒂亚送到目的地，则输出 “-1”（不带引号）。否则，输出行程的最小费用。

在 C++ 中，请勿使用 %lld 格式说明符读取或写入 64 位整数。推荐使用 cin、cout 流，或 %I64d 格式说明符。

An optimal way — ride from the junction 1 to 2 (via junction 4), then from 2 to 3. It costs 7+2=9 bourles.

一种最优方案：从路口 1 出发，经路口 4 到达路口 2，再从路口 2 到达路口 3。总花费为 $7+2=9$ 布尔币。