{"problem":{"name":"C. Volleyball","description":{"content":"Petya loves volleyball very much. One day he was running late for a volleyball match. Petya hasn't bought his own car yet, that's why he had to take a taxi. The city has _n_ junctions, some of which a","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF95C"},"statements":[{"statement_type":"Markdown","content":"Petya loves volleyball very much. One day he was running late for a volleyball match. Petya hasn't bought his own car yet, that's why he had to take a taxi. The city has _n_ junctions, some of which are connected by two-way roads. The length of each road is defined by some positive integer number of meters; the roads can have different lengths.\n\nInitially each junction has exactly one taxi standing there. The taxi driver from the _i_\\-th junction agrees to drive Petya (perhaps through several intermediate junctions) to some other junction if the travel distance is not more than _t__i_ meters. Also, the cost of the ride doesn't depend on the distance and is equal to _c__i_ bourles. Taxis can't stop in the middle of a road. **Each taxi can be used no more than once. Petya can catch taxi only in the junction, where it stands initially.**\n\nAt the moment Petya is located on the junction _x_ and the volleyball stadium is on the junction _y_. Determine the minimum amount of money Petya will need to drive to the stadium.\n\n## Input\n\nThe first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 1000, 0 ≤ _m_ ≤ 1000). They are the number of junctions and roads in the city correspondingly. The junctions are numbered from 1 to _n_, inclusive. The next line contains two integers _x_ and _y_ (1 ≤ _x_, _y_ ≤ _n_). They are the numbers of the initial and final junctions correspondingly. Next _m_ lines contain the roads' description. Each road is described by a group of three integers _u__i_, _v__i_, _w__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_, 1 ≤ _w__i_ ≤ 109) — they are the numbers of the junctions connected by the road and the length of the road, correspondingly. The next _n_ lines contain _n_ pairs of integers _t__i_ and _c__i_ (1 ≤ _t__i_, _c__i_ ≤ 109), which describe the taxi driver that waits at the _i_\\-th junction — the maximum distance he can drive and the drive's cost. The road can't connect the junction with itself, but between a pair of junctions there can be more than one road. All consecutive numbers in each line are separated by exactly one space character.\n\n## Output\n\nIf taxis can't drive Petya to the destination point, print \"-1\" (without the quotes). Otherwise, print the drive's minimum cost.\n\nPlease do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d specificator.\n\n[samples]\n\n## Note\n\nAn optimal way — ride from the junction 1 to 2 (via junction 4), then from 2 to 3. It costs 7+2=9 bourles.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Petya 非常喜欢排球。一天，他赶往排球比赛时迟到了。Petya 还没有买自己的车，因此他不得不打出租车。这座城市有 #cf_span[n] 个交叉口，其中一些由双向道路连接。每条道路的长度由某个正整数（单位：米）定义；道路长度可以不同。\n\n最初，每个交叉口恰好有一辆出租车停在那里。第 #cf_span[i] 个交叉口的司机同意搭载 Petya（可能经过若干中间交叉口）前往另一个交叉口，前提是行驶距离不超过 #cf_span[ti] 米。此外，车费与距离无关，固定为 #cf_span[ci] 布尔。出租车不能在道路中间停下。*每辆出租车最多只能使用一次。Petya 只能在出租车初始所在的交叉口上车。*\n\n目前 Petya 位于交叉口 #cf_span[x]，排球馆位于交叉口 #cf_span[y]。请确定 Petya 到达场馆所需的最少费用。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000]），分别表示城市中的交叉口数量和道路数量。交叉口编号从 #cf_span[1] 到 #cf_span[n]。下一行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ n]），分别表示起始和终点交叉口。接下来 #cf_span[m] 行描述道路，每条道路由三个整数 #cf_span[ui], #cf_span[vi], #cf_span[wi]（#cf_span[1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 10^9]）描述，分别表示连接的两个交叉口及其道路长度。接下来 #cf_span[n] 行包含 #cf_span[n] 对整数 #cf_span[ti] 和 #cf_span[ci]（#cf_span[1 ≤ ti, ci ≤ 10^9]），描述位于第 #cf_span[i] 个交叉口的司机：他能行驶的最大距离和车费。道路不会连接交叉口与自身，但一对交叉口之间可能存在多条道路。每行中相邻数字之间恰好用一个空格分隔。\n\n如果出租车无法将 Petya 送达目的地，请输出 \"-1\"（不含引号）。否则，输出最小车费。\n\n请勿在 C++ 中使用 %lld 格式符读写 64 位整数。推荐使用 cin、cout 流或 %I64d 格式符。\n\n最优方案：从交叉口 1 到 2（经由交叉口 4），再从 2 到 3。总费用为 7+2=9 布尔。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 1000, 0 ≤ m ≤ 1000]），分别表示城市中的交叉口数量和道路数量。交叉口编号从 #cf_span[1] 到 #cf_span[n]。下一行包含两个整数 #cf_span[x] 和 #cf_span[y]（#cf_span[1 ≤ x, y ≤ n]），分别表示起始和终点交叉口。接下来 #cf_span[m] 行描述道路，每条道路由三个整数 #cf_span[ui], #cf_span[vi], #cf_span[wi]（#cf_span[1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 10^9]）描述，分别表示连接的两个交叉口及其道路长度。接下来 #cf_span[n] 行包含 #cf_span[n] 对整数 #cf_span[ti] 和 #cf_span[ci]（#cf_span[1 ≤ ti, ci ≤ 10^9]），描述位于第 #cf_span[i] 个交叉口的司机：他能行驶的最大距离和车费。道路不会连接交叉口与自身，但一对交叉口之间可能存在多条道路。每行中相邻数字之间恰好用一个空格分隔。\n\n## Output\n\n如果出租车无法将 Petya 送达目的地，请输出 \"-1\"（不含引号）。否则，输出最小车费。请勿在 C++ 中使用 %lld 格式符读写 64 位整数。推荐使用 cin、cout 流或 %I64d 格式符。\n\n[samples]\n\n## Note\n\n最优方案：从交叉口 1 到 2（经由交叉口 4），再从 2 到 3。总费用为 7+2=9 布尔。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ be the number of junctions and roads, respectively.  \nLet $ G = (V, E) $ be an undirected weighted graph with $ V = \\{1, 2, \\dots, n\\} $ and $ E \\subseteq V \\times V $, where each edge $ (u, v) \\in E $ has weight $ w(u, v) \\in \\mathbb{Z}^+ $.  \nLet $ x, y \\in V $ be the source and target junctions, respectively.  \nFor each junction $ i \\in V $, let $ t_i \\in \\mathbb{Z}^+ $ be the maximum travel distance and $ c_i \\in \\mathbb{Z}^+ $ be the cost of the taxi available at $ i $.  \n\nLet $ d(i, j) \\in \\mathbb{R}_{\\geq 0} \\cup \\{\\infty\\} $ denote the shortest path distance (in meters) between junctions $ i $ and $ j $ in $ G $, computed using all roads.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 1000 $, $ 0 \\leq m \\leq 1000 $  \n2. $ 1 \\leq x, y \\leq n $  \n3. $ 1 \\leq w(u, v) \\leq 10^9 $ for all edges $ (u, v) $  \n4. $ 1 \\leq t_i, c_i \\leq 10^9 $ for all $ i \\in V $  \n5. Each taxi at junction $ i $ can be used at most once.  \n6. Petya can only board a taxi at its initial junction $ i $.  \n7. A taxi at $ i $ can take Petya to junction $ j $ **iff** $ d(i, j) \\leq t_i $.  \n\n**Objective**  \nFind the minimum total cost to travel from $ x $ to $ y $, using a sequence of taxis (each used at most once), such that:  \n- The first taxi is boarded at $ x $.  \n- Each subsequent taxi is boarded at the junction where the previous taxi dropped Petya.  \n- The final junction is $ y $.  \n\nFormally, find the minimum value of $ \\sum_{k=1}^{\\ell} c_{i_k} $ over all sequences $ i_1 = x, i_2, \\dots, i_\\ell $ such that:  \n- $ d(i_k, i_{k+1}) \\leq t_{i_k} $ for all $ k \\in \\{1, \\dots, \\ell-1\\} $,  \n- $ i_\\ell = y $,  \n- All $ i_k \\in V $ are distinct (each taxi used at most once).  \n\nIf no such sequence exists, output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF95C","tags":["shortest paths"],"sample_group":[["4 4\n1 3\n1 2 3\n1 4 1\n2 4 1\n2 3 5\n2 7\n7 2\n1 2\n7 7","9"]],"created_at":"2026-03-03 11:00:39"}}