本题数据量较大，请用较快的读入方式

Petya 非常喜欢排球。有一天，他参加排球比赛迟到了。Petya 还没有买车，所以只能打车。城市里有 n 个交叉路口，其中一些由双向道路连接。每条道路的长度由某个正整数米定义，且道路的长度可能不同。

最初，每个路口正好有一辆出租车停在那里。如果从第 i 个路口出发，到达其他路口的距离不超过 $t_i$ 米，来自第 i 个路口的出租车司机同意载 Petya（可能经过几个中间路口）到其他路口。此外，车费与距离无关，等于 $c_i$。出租车不能在中途停车，并且每辆出租车只能使用一次，Petya 只能在最初停靠的路口搭乘出租车。

Petya 当前位于路口 x，排球场位于路口 y。请计算 Petya 开车去排球场所需的最低费用。

输入格式

• 从文件d.in 中读入数据。

• 第一行包含两个整数 n 和 m (1 ≤ n ≤ 5000, 0 ≤ m ≤ 20000)，分别表示城市中的路口数量和道路数量。路口编号从 1 到 n。

• 第二行包含两个整数 x 和 y (1 ≤ x, y ≤ n)，分别表示 Petya 当前所在的起始路口和排球场所在的目的路口。

• 接下来的 m 行，每行包含三个整数 $u_i, v_i, w_i (1 ≤ u_i, v_i ≤n, 1 ≤w_i ≤ 10^9)$，分别表示一条连接路口 $u_i$ 和 $v_i$ 的道路及其长度（米）。

• 接下来的 n 行，每行包含两个整数 $t_i$ 和 $c_i$ $(1 ≤ t_i, c_i ≤ 10^9)$，分别表示在第 i 个路口等待的出租车能行驶的最大距离以及车费。

输出格式

如果出租车无法将 Petya 送到目的地，则打印 -1。否则，打印 Petya 到达排球场所需的最低费用。

输入样例

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

说明

一种最佳方式是：从 1 号路口到 2 号路口（经过 4 号路口），然后从 2 号路口到 3 号路口，总费用为 9。

数据范围

• 对于 20% 的数据，满足：

  $1 \leq n \leq 100$

  $1 \leq m \leq 1000$

• 对于50%的数据， 满足：

  $1 \leq n \leq 1000$

  $1 \leq m \leq 10000$

• 对于 100% 的数据，满足：

  $1 \leq n \leq 5000$

  $0 \leq m \leq 20000$

  $1 \leq t_i, c_i \leq 10^9$

  $1 \leq w_i \leq 10^9$