← 返回题目列表

Codeforces · 95/C

C. 排球

中文机器翻译题面 查看原题

Petya非常喜欢排球。有一天,他参加一场排球比赛迟到了。 Petya还没有买自己的车,所以他不得不乘坐出租车。城市有n个路口,其中一些路口由双向道路连接。每条道路的长度由某个正整数米定义;道路可以有不同的长度。

最初,每个路口都只有一辆出租车停在那里。如果行驶距离不超过 ti 米,来自第 i 个路口的出租车司机同意将 Petya(可能经过几个中间路口)开往其他路口。此外,乘车费用与距离无关,等于 ci bourles。出租车不能停在路中间。每辆出租车只能使用一次。 Petya 只能在交叉路口(最初所在的位置)搭乘出租车。

目前 Petya 位于交叉路口 x,排球场位于交叉路口 y。确定 Petya 开车前往体育场所需的最低金额。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000)。它们分别是城市中路口和道路的数量。结点编号为从 1 到 n(含 1 和 n)。下一行包含两个整数 x 和 y (1 ≤ x, y ≤ n)。它们分别是起始和最终路口的编号。接下来的 m 行包含道路的描述。每条道路由一组三个整数 ui, vi, wi (1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 109) 描述——它们分别是道路连接的路口的数量和道路的长度。接下来的n行包含n对整数ti和ci(1≤ti,ci≤109),它们描述了在第i个路口等待的出租车司机——他可以行驶的最大距离和行驶成本。道路无法将交汇点与其本身连接起来,但在一对交汇点之间可以有多条道路。每行中的所有连续数字均由一个空格字符分隔。

输出

如果出租车无法将 Petya 送到目的地,请打印“-1”(不带引号)。否则,打印驱动器的最低成本。

请不要使用 %lld 说明符在 С++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 指定器。

示例

输入 #1

4 4
1 3
1 2 3
1 4 1
2 4 1
2 3 5
2 7
7 2
1 2
7 7

输出 #1

9

注意

最佳方式 — 从 1 号路口骑行到 2 号路口(经过 4 号路口),然后从 2 号到 3 号路。花费 7+2=9 布尔。