English · Original
Chinese · Translation
Formal · Original
ZS the Coder has drawn an undirected graph of _n_ vertices numbered from 0 to _n_ - 1 and _m_ edges between them. Each edge of the graph is weighted, each weight is a **positive integer**.
The next day, ZS the Coder realized that some of the weights were erased! So he wants to reassign **positive integer** weight to each of the edges which weights were erased, so that the length of the shortest path between vertices _s_ and _t_ in the resulting graph is exactly _L_. Can you help him?
## Input
The first line contains five integers _n_, _m_, _L_, _s_, _t_ (2 ≤ _n_ ≤ 1000, 1 ≤ _m_ ≤ 10 000, 1 ≤ _L_ ≤ 109, 0 ≤ _s_, _t_ ≤ _n_ - 1, _s_ ≠ _t_) — the number of vertices, number of edges, the desired length of shortest path, starting vertex and ending vertex respectively.
Then, _m_ lines describing the edges of the graph follow. _i_\-th of them contains three integers, _u__i_, _v__i_, _w__i_ (0 ≤ _u__i_, _v__i_ ≤ _n_ - 1, _u__i_ ≠ _v__i_, 0 ≤ _w__i_ ≤ 109). _u__i_ and _v__i_ denote the endpoints of the edge and _w__i_ denotes its weight. If _w__i_ is equal to 0 then the weight of the corresponding edge was erased.
It is guaranteed that there is at most one edge between any pair of vertices.
## Output
Print "_NO_" (without quotes) in the only line if it's not possible to assign the weights in a required way.
Otherwise, print "_YES_" in the first line. Next _m_ lines should contain the edges of the resulting graph, with weights assigned to edges which weights were erased. _i_\-th of them should contain three integers _u__i_, _v__i_ and _w__i_, denoting an edge between vertices _u__i_ and _v__i_ of weight _w__i_. The edges of the new graph must coincide with the ones in the graph from the input. The weights that were not erased must remain unchanged whereas the new weights can be any **positive integer** not exceeding 1018.
The order of the edges in the output doesn't matter. The length of the shortest path between _s_ and _t_ must be equal to _L_.
If there are multiple solutions, print any of them.
[samples]
## Note
Here's how the graph in the first sample case looks like :
<center></center>In the first sample case, there is only one missing edge weight. Placing the weight of 8 gives a shortest path from 0 to 4 of length 13.
In the second sample case, there is only a single edge. Clearly, the only way is to replace the missing weight with 123456789.
In the last sample case, there is no weights to assign but the length of the shortest path doesn't match the required value, so the answer is "_NO_".
ZS the Coder 画了一个无向图，包含 #cf_span[n] 个顶点，编号从 #cf_span[0] 到 #cf_span[n - 1]，以及 #cf_span[m] 条边。图中每条边都有一个权重，且每个权重都是一个*正整数*。
第二天，ZS the Coder 发现某些边的权重被擦除了！因此，他希望为所有权重被擦除的边重新分配*正整数*权重，使得在最终图中，顶点 #cf_span[s] 和 #cf_span[t] 之间的最短路径长度恰好为 #cf_span[L]。你能帮助他吗？
第一行包含五个整数 #cf_span[n, m, L, s, t]（#cf_span[2 ≤ n ≤ 1000, 1 ≤ m ≤ 10 000, 1 ≤ L ≤ 109, 0 ≤ s, t ≤ n - 1, s ≠ t]）——分别表示顶点数、边数、期望的最短路径长度、起始顶点和终止顶点。
接下来是 #cf_span[m] 行，描述图中的边。第 #cf_span[i] 行包含三个整数 #cf_span[ui, vi, wi]（#cf_span[0 ≤ ui, vi ≤ n - 1, ui ≠ vi, 0 ≤ wi ≤ 109]）。其中 #cf_span[ui] 和 #cf_span[vi] 表示边的两个端点，#cf_span[wi] 表示其权重。如果 #cf_span[wi] 等于 #cf_span[0]，则表示该边的权重被擦除了。
保证任意两个顶点之间至多有一条边。
如果无法按要求分配权重，请在唯一一行中输出 "_NO_"（不含引号）。
否则，第一行输出 "_YES_"。接下来的 #cf_span[m] 行应输出最终图的边，其中被擦除的边的权重已被赋值。第 #cf_span[i] 行应包含三个整数 #cf_span[ui]、#cf_span[vi] 和 #cf_span[wi]，表示连接顶点 #cf_span[ui] 和 #cf_span[vi]、权重为 #cf_span[wi] 的边。新图的边必须与输入图中的边完全一致。未被擦除的权重必须保持不变，而新分配的权重可以是任意不超过 #cf_span[1018] 的*正整数*。
输出边的顺序无关紧要。顶点 #cf_span[s] 和 #cf_span[t] 之间的最短路径长度必须等于 #cf_span[L]。
如果存在多个解，输出任意一个即可。
第一个样例中图的结构如下：
在第一个样例中，只有一个缺失的边权重。将该边权重设为 #cf_span[8]，则从 #cf_span[0] 到 #cf_span[4] 的最短路径长度为 #cf_span[13]。
在第二个样例中，仅有一条边。显然，唯一的方法是将缺失的权重替换为 #cf_span[123456789]。
在最后一个样例中，没有需要分配的权重，但最短路径长度与要求值不匹配，因此答案为 "_NO_"。
## Input
第一行包含五个整数 #cf_span[n, m, L, s, t]（#cf_span[2 ≤ n ≤ 1000, 1 ≤ m ≤ 10 000, 1 ≤ L ≤ 109, 0 ≤ s, t ≤ n - 1, s ≠ t]）——分别表示顶点数、边数、期望的最短路径长度、起始顶点和终止顶点。接下来是 #cf_span[m] 行，描述图中的边。第 #cf_span[i] 行包含三个整数 #cf_span[ui, vi, wi]（#cf_span[0 ≤ ui, vi ≤ n - 1, ui ≠ vi, 0 ≤ wi ≤ 109]）。#cf_span[ui] 和 #cf_span[vi] 表示边的两个端点，#cf_span[wi] 表示其权重。如果 #cf_span[wi] 等于 #cf_span[0]，则表示该边的权重被擦除了。保证任意两个顶点之间至多有一条边。
## Output
如果无法按要求分配权重，请在唯一一行中输出 "_NO_"（不含引号）。否则，第一行输出 "_YES_"。接下来的 #cf_span[m] 行应输出最终图的边，其中被擦除的边的权重已被赋值。第 #cf_span[i] 行应包含三个整数 #cf_span[ui]、#cf_span[vi] 和 #cf_span[wi]，表示连接顶点 #cf_span[ui] 和 #cf_span[vi]、权重为 #cf_span[wi] 的边。新图的边必须与输入图中的边完全一致。未被擦除的权重必须保持不变，而新分配的权重可以是任意不超过 #cf_span[1018] 的*正整数*。输出边的顺序无关紧要。顶点 #cf_span[s] 和 #cf_span[t] 之间的最短路径长度必须等于 #cf_span[L]。如果存在多个解，输出任意一个即可。
[samples]
## Note
第一个样例中图的结构如下：
在第一个样例中，只有一个缺失的边权重。将该边权重设为 #cf_span[8]，则从 #cf_span[0] 到 #cf_span[4] 的最短路径长度为 #cf_span[13]。
在第二个样例中，仅有一条边。显然，唯一的方法是将缺失的权重替换为 #cf_span[123456789]。
在最后一个样例中，没有需要分配的权重，但最短路径长度与要求值不匹配，因此答案为 "_NO_"。
**Definitions:**
- Let $ G = (V, E) $ be an undirected graph with $ |V| = n $, $ |E| = m $.
- Vertices are labeled $ 0 $ to $ n-1 $.
- Each edge $ e = (u, v) \in E $ has a weight $ w(e) \in \mathbb{Z}^+ \cup \{0\} $, where $ w(e) = 0 $ indicates the weight is erased (to be assigned).
- Given: source vertex $ s $, target vertex $ t $, desired shortest path length $ L \in \mathbb{Z}^+ $.
**Constraints:**
1. For each edge $ e = (u, v, w) $:
- If $ w > 0 $, then $ w(e) = w $ (fixed).
- If $ w = 0 $, then $ w(e) \in \mathbb{Z}^+ $ and $ w(e) \leq 10^{18} $ (to be assigned).
2. Let $ d_G(s, t) $ denote the shortest path distance from $ s $ to $ t $ in the resulting graph with assigned weights.
- Require: $ d_G(s, t) = L $.
**Objective:**
Determine whether there exists an assignment of positive integer weights to all erased edges (with values $ \leq 10^{18} $) such that the shortest path from $ s $ to $ t $ is exactly $ L $. If yes, output one such assignment; otherwise, output "NO".
**Formal Problem Statement:**
Given:
- $ n, m, L, s, t \in \mathbb{Z}^+ $, with $ 2 \leq n \leq 1000 $, $ 1 \leq m \leq 10000 $, $ 1 \leq L \leq 10^9 $, $ 0 \leq s, t \leq n-1 $, $ s \ne t $.
- A multiset of edges $ E = \{ (u_i, v_i, w_i) \}_{i=1}^m $, where $ w_i \in \{0\} \cup [1, 10^9] $, and $ w_i = 0 $ iff the edge weight is erased.
Find:
- An assignment $ w': E \to \mathbb{Z}^+ $ such that:
- $ w'(e) = w(e) $ for all $ e \in E $ with $ w(e) > 0 $,
- $ w'(e) \in [1, 10^{18}] $ for all $ e \in E $ with $ w(e) = 0 $,
- $ \text{dist}_{G'}(s, t) = L $, where $ G' = (V, E, w') $.
Output:
- "NO" if no such assignment exists.
- "YES" followed by the list of edges with assigned weights otherwise.
API Response (JSON)
{
"problem": {
"name": "D. Complete The Graph",
"description": {
"content": "ZS the Coder has drawn an undirected graph of _n_ vertices numbered from 0 to _n_ - 1 and _m_ edges between them. Each edge of the graph is weighted, each weight is a **positive integer**. The next d",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 4000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF716D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "ZS the Coder has drawn an undirected graph of _n_ vertices numbered from 0 to _n_ - 1 and _m_ edges between them. Each edge of the graph is weighted, each weight is a **positive integer**.\n\nThe next d...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "ZS the Coder 画了一个无向图，包含 #cf_span[n] 个顶点，编号从 #cf_span[0] 到 #cf_span[n - 1]，以及 #cf_span[m] 条边。图中每条边都有一个权重，且每个权重都是一个*正整数*。\n\n第二天，ZS the Coder 发现某些边的权重被擦除了！因此，他希望为所有权重被擦除的边重新分配*正整数*权重，使得在最终图中，顶点 #cf_span[s...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions:**\n\n- Let $ G = (V, E) $ be an undirected graph with $ |V| = n $, $ |E| = m $.\n- Vertices are labeled $ 0 $ to $ n-1 $.\n- Each edge $ e = (u, v) \\in E $ has a weight $ w(e) \\in \\mathbb{Z...",
"is_translate": false,
"language": "Formal"
}
]
}