CF95C Volleyball

Petya 非常热爱排球。有一天他去看排球比赛快迟到了。由于还没买车，他只好叫出租车。这座城市有 $n$ 个十字路口，部分路口由双向道路连接。每条道路的长度以正整数米为单位，不同道路长度可能不同。 最初每个十字路口都停着一辆出租车。位于第 $i$ 个路口的司机愿意载 Petya 前往其他路口（可途经多个路口），只要行驶总距离不超过 $t_i$ 米。车费与距离无关，固定为 $c_i$ 布尔。出租车不能在道路中途停靠。每辆出租车最多只能使用一次。Petya 只能在出租车初始停靠的路口搭乘。 现在 Petya 位于 $x$ 号路口，排球馆在 $y$ 号路口。请计算 Petya 到达球场所需的最低费用。

第一行两个整数 $n$ 和 $m$（$1 \le n \le 1000, 0 \le m \le 1000$），分别表示城市中的路口数量和道路数量，路口编号为 $1 \sim n$。 第二行两个整数 $x$ 和 $y$（$1 \le x, y \le n$），表示起点和终点路口编号。 接下来 $m$ 行描述道路信息，每行三个整数 $u_i,v_i,w_i$（$1 \le u_i,v_i \le n, 1 \le w_i \le 10^9$），表示相连的两个路口编号及道路长度。 最后 $n$ 行给出 $n$ 组整数 $t_i$ 和 $c_i$（$1 \le t_i,c_i \le 10^9$），描述第 $i$ 个路口出租车的最大行驶距离和车费。道路不会连接相同路口，但两个路口间可能存在多条道路。

若无法乘出租车到达目的地，输出 `-1`，否则输出最低费用。

样例解释： 最优路线为从 $1$ 号路口经 $4$ 号路口到 $2$ 号路口，再从 $2$ 号路口到 $3$ 号路口。总费用 $7 + 2 = 9$ 布尔。 Translate by @[Moya_Rao](https://www.luogu.com.cn/user/814130)