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.
## Input
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.
## Output
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.
[samples]
## Note
An optimal way — ride from the junction 1 to 2 (via junction 4), then from 2 to 3. It costs 7+2=9 bourles.
Petya 非常喜欢排球。一天，他赶着去参加一场排球比赛，但迟到了。Petya 还没有买自己的车，因此他不得不打出租车。这座城市有 #cf_span[n] 个交叉口，其中一些由双向道路连接。每条道路的长度由某个正整数（单位：米）定义；道路长度可以不同。
最初，每个交叉口都恰好有一辆出租车停在那里。第 #cf_span[i] 个交叉口的出租车司机同意搭载 Petya（可能经过若干中间交叉口）前往另一个交叉口，前提是行驶距离不超过 #cf_span[ti] 米。此外，车费与距离无关，固定为 #cf_span[ci] 布尔。出租车不能在道路中间停下。*每辆出租车最多只能使用一次。Petya 只能在出租车初始停靠的交叉口上车。*
目前，Petya 位于交叉口 #cf_span[x]，排球馆位于交叉口 #cf_span[y]。请确定 Petya 到达体育馆所需的最少费用。
第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000]），分别表示城市中的交叉口数量和道路数量。交叉口编号从 #cf_span[1] 到 #cf_span[n]。下一行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ n]），分别表示初始交叉口和目标交叉口。接下来的 #cf_span[m] 行描述道路：每条道路由三个整数 #cf_span[ui], #cf_span[vi], #cf_span[wi]（#cf_span[1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 10^9]）描述，分别表示道路连接的两个交叉口及其长度。接下来的 #cf_span[n] 行包含 #cf_span[n] 对整数 #cf_span[ti] 和 #cf_span[ci]（#cf_span[1 ≤ ti, ci ≤ 10^9]），描述在第 #cf_span[i] 个交叉口等待的出租车司机：他能行驶的最大距离和车费。道路不会连接同一个交叉口，但两个交叉口之间可能存在多条道路。每行中相邻的数字之间恰好用一个空格分隔。
如果出租车无法将 Petya 送到目的地，请输出 "-1"（不含引号）。否则，请输出最小车费。
请勿在 C++ 中使用 %lld 格式说明符读写 64 位整数。建议使用 cin、cout 流或 %I64d 格式说明符。
最优方案：从交叉口 1 到 2（经由交叉口 4），然后从 2 到 3。总费用为 7+2=9 布尔。
## Input
第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000]），分别表示城市中的交叉口数量和道路数量。交叉口编号从 #cf_span[1] 到 #cf_span[n]。下一行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ n]），分别表示初始交叉口和目标交叉口。接下来的 #cf_span[m] 行描述道路：每条道路由三个整数 #cf_span[ui], #cf_span[vi], #cf_span[wi]（#cf_span[1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 10^9]）描述，分别表示道路连接的两个交叉口及其长度。接下来的 #cf_span[n] 行包含 #cf_span[n] 对整数 #cf_span[ti] 和 #cf_span[ci]（#cf_span[1 ≤ ti, ci ≤ 10^9]），描述在第 #cf_span[i] 个交叉口等待的出租车司机：他能行驶的最大距离和车费。道路不会连接同一个交叉口，但两个交叉口之间可能存在多条道路。每行中相邻的数字之间恰好用一个空格分隔。
## Output
如果出租车无法将 Petya 送到目的地，请输出 "-1"（不含引号）。否则，请输出最小车费。请勿在 C++ 中使用 %lld 格式说明符读写 64 位整数。建议使用 cin、cout 流或 %I64d 格式说明符。
[samples]
## Note
最优方案：从交叉口 1 到 2（经由交叉口 4），然后从 2 到 3。总费用为 7+2=9 布尔。
**Definitions**
Let $ n, m \in \mathbb{Z} $ be the number of junctions and roads.
Let $ G = (V, E) $ be an undirected weighted graph with $ V = \{1, 2, \dots, n\} $ and $ E \subseteq V \times V $, where each edge $ (u, v) \in E $ has weight $ w(u, v) \in \mathbb{Z}^+ $.
Let $ x, y \in V $ be the source and target junctions.
For each junction $ i \in V $, let $ t_i \in \mathbb{Z}^+ $ be the maximum travel distance and $ c_i \in \mathbb{Z}^+ $ be the fixed cost of the taxi available at $ i $.
**Constraints**
1. $ 1 \le n \le 1000 $, $ 0 \le m \le 1000 $
2. $ 1 \le x, y \le n $
3. For each road $ (u_i, v_i, w_i) $: $ 1 \le u_i, v_i \le n $, $ 1 \le w_i \le 10^9 $
4. For each junction $ i $: $ 1 \le t_i, c_i \le 10^9 $
5. Multiple edges between same pair of junctions allowed.
6. No self-loops.
**Objective**
Compute the minimum total cost to travel from $ x $ to $ y $ using taxis, where:
- Petya starts at $ x $, must reach $ y $.
- At each junction $ i $, Petya may take the taxi only once, and only if the shortest path distance from $ i $ to some junction $ j $ is $ \le t_i $.
- Taking taxi at $ i $ to go to $ j $ costs $ c_i $ bourles, regardless of distance (as long as $ \text{dist}(i, j) \le t_i $).
- Each taxi can be used at most once.
- Petya can only board a taxi at the junction where it initially stands.
Define $ d(i, j) $ as the shortest path distance (in meters) between junctions $ i $ and $ j $ in $ G $.
Define a directed graph $ H = (V, E_H) $, where $ (i, j) \in E_H $ iff $ d(i, j) \le t_i $ and $ i \ne j $.
Each edge $ (i, j) \in E_H $ has cost $ c_i $.
Find the minimum cost path from $ x $ to $ y $ in $ H $, where path cost is sum of edge costs.
If no such path exists, output $ -1 $.
**Formal Objective**
$$
\min \left\{ \sum_{k=1}^{|P|-1} c_{p_k} \,\middle|\, P = (p_1, p_2, \dots, p_{|P|}) \text{ is a path in } H, p_1 = x, p_{|P|} = y \right\}
$$
If the set is empty, output $ -1 $.