{"problem":{"name":"D. 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":"CF96D"},"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.  \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.  \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 fixed cost of the taxi available at $ i $.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 1000 $, $ 0 \\le m \\le 1000 $  \n2. $ 1 \\le x, y \\le n $  \n3. For each road $ (u_i, v_i, w_i) $: $ 1 \\le u_i, v_i \\le n $, $ 1 \\le w_i \\le 10^9 $  \n4. For each junction $ i $: $ 1 \\le t_i, c_i \\le 10^9 $  \n5. Multiple edges between same pair of junctions allowed.  \n6. No self-loops.  \n\n**Objective**  \nCompute the minimum total cost to travel from $ x $ to $ y $ using taxis, where:  \n- Petya starts at $ x $, must reach $ y $.  \n- At each junction $ i $, Petya may take the taxi only once, and only if the shortest path distance from $ i $ to some junction $ j $ is $ \\le t_i $.  \n- Taking taxi at $ i $ to go to $ j $ costs $ c_i $ bourles, regardless of distance (as long as $ \\text{dist}(i, j) \\le t_i $).  \n- Each taxi can be used at most once.  \n- Petya can only board a taxi at the junction where it initially stands.  \n\nDefine $ d(i, j) $ as the shortest path distance (in meters) between junctions $ i $ and $ j $ in $ G $.  \nDefine a directed graph $ H = (V, E_H) $, where $ (i, j) \\in E_H $ iff $ d(i, j) \\le t_i $ and $ i \\ne j $.  \nEach edge $ (i, j) \\in E_H $ has cost $ c_i $.  \n\nFind the minimum cost path from $ x $ to $ y $ in $ H $, where path cost is sum of edge costs.  \nIf no such path exists, output $ -1 $.  \n\n**Formal Objective**  \n$$\n\\min \\left\\{ \\sum_{k=1}^{|P|-1} c_{p_k} \\,\\middle|\\, P = (p_1, p_2, \\dots, p_{|P|}) \\text{ is a path in } H, p_1 = x, p_{|P|} = y \\right\\}\n$$  \nIf the set is empty, output $ -1 $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF96D","tags":["graphs","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"}}