{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"老王非常喜欢国足。一天,他要去观看一场足球比赛。由于老王很穷,并且没有车子,所以他能骑共享单车。这个城市有 $n$ 个路口,其中一些道路由双向连接。每路口之间的长度由若干米的正整数定义,路口之间可以有不同的长度。\n\n最初,每个路口只有一辆共享单车停在那里。从第 i 个路口出发,由于每个共享单车电量不唯一,即所行驶距离不超过 $t_i$ 米,老王骑车(可能要经过几个中间路口)到其他路口。 此外,乘坐的费用不取决于距离,而是等于 $c_i$ 元。由于道路中间没有共享单车,即老王不能停在路中间。每辆单车只能使用一次,开始老王只能从他最初所在的路口使用共享单车到其他路口(随后可以多次换乘)。\n\n目前老王位于 $x$ 路口,足球场位于 $y$ 路口,请你帮助老王确定骑车到球场需要的最低金额。"}},{"title":"Input","value":{"format":"MD","content":"第一行输入包含 $2$ 个整数 $n,m (1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000)$,分别对应的是城市中路口与路口之间道路的数量。路口编号范围是从 $1$ 到 $n$。\n\n接下来的一行包含 $2$ 个整数 $x, y (1 ≤ x, y ≤ n)$,它们分别是初始路口和终点路口的编号。\n\n接下来的 $m$ 行包含道路的描述。 每条路由 $3$ 个整数描述: $u_i, v_i, w_i (1 ≤ u_i, v_i ≤ n, 1 ≤ w_i ≤ 10^9)$,他们分别代表道路连接的路口编号和道路长度。\n\n接下来的 $n$ 行包含 $n$ 对整数 $t_i,c_i (1 ≤ ti, ci ≤ 10^9)$,描述了在第 $i$ 个路口的共享单车所能到达的最远距离和所需要花费的金额。\n\n一条路不可能只连接 $1$ 个路口,但是在一对路口之间可以有不止一条路。\n每一行中的所有连续数字都由一个空格字符分隔。"}},{"title":"Output","value":{"format":"MD","content":"如果老王不能到达终点,输出 $-1$,否则,输出最少花费的金额。\n\n在C++中请不要用 %lld 说明符读取或写入 $64$ 位整数,推荐使用标准输入输出流 cin, cout 或者 %I64d 说明符。"}},{"title":"Smaple","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 4\n1 3\n1 2 3\n1 4 1\n2 4 1\n2 3 5\n2 7\n7 2\n1 2\n7 7\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"提示","value":{"format":"MD","content":"最佳路径:从路口 1 到路口 2 (经过路口 4),然后从路口 2 到路口3,共花费 7+2\u003d9 元。"}}]}