该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

排球

题目描述

Petya 非常喜欢排球。有一天，他赶着去参加一场排球比赛。Petya 还没有买自己的车，所以他不得不乘坐出租车。这座城市有 $n$ 个路口，其中一些路口通过双向道路相连。每条道路的长度由某个正整数（米）定义，道路可以有不同的长度。

最初，每个路口都有一辆出租车停在那里。来自第 $i$ 个路口的出租车司机同意开车送 Petya（可能经过几个中间路口）到另一个路口，只要行驶距离不超过 $t_{i}$ 米。此外，乘车费用与距离无关，等于 $c_{i}$ 卢布。出租车不能在道路中间停车。每辆出租车最多只能使用一次。Petya 只能在出租车最初停靠的路口上车。

现在 Petya 位于路口 $x$，而排球场位于路口 $y$。确定 Petya 到达体育场所需的最小金额。

输入格式

第一行包含两个整数 $n$ 和 $m$（$1<=n<=1000, 0<=m<=1000$）。它们分别是城市中的路口数和道路数。路口从 $1$ 到 $n$ 编号，包括 $n$。下一行包含两个整数 $x$ 和 $y$（$1<=x,y<=n$）。它们分别是起始路口和终点路口的编号。接下来的 $m$ 行包含道路的描述。每条道路由三个整数 $u_{i}$，$v_{i}$，$w_{i}$（$1<=u_{i},v_{i}<=n, 1<=w_{i}<=10^{9}$）描述，分别是道路连接的路口编号和道路的长度。接下来的 $n$ 行包含 $n$ 对整数 $t_{i}$ 和 $c_{i}$（$1<=t_{i},c_{i}<=10^{9}$），它们描述了在第 $i$ 个路口等待的出租车司机——他最多可以行驶的距离和乘车费用。道路不能连接路口到自身，但一对路口之间可以有多条道路。每行中的连续数字之间用恰好一个空格字符分隔。

输出格式

如果出租车无法将 Petya 送到目的地，则打印 "-1"（不带引号）。否则，打印乘车的最小费用。

在 C++ 中读取或写入 64 位整数时，请不要使用 %lld 说明符。建议使用 cin、cout 流或 %I64d 说明符。

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。费用为 7+2=9 卢布。