CF715B.Complete The Graph

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?

ZS 这位程序员画出了一个包含 $n$ 个顶点（编号从 $0$ 到 $n-1$）和 $m$ 条边的无向图。图中的每条边都带有权重，且每个权重均为正整数。

第二天，ZS 发现其中一些边的权重被擦除了！因此，他希望为所有被擦除权重的边重新赋以正整数权重，使得最终图中顶点 $s$ 与 $t$ 之间的最短路径长度恰好为 $L$。你能帮他实现吗？

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.

第一行包含五个整数 $n$、$m$、$L$、$s$、$t$（$2 \leq n \leq 1000$，$1 \leq m \leq 10\,000$，$1 \leq L \leq 10^9$，$0 \leq s, t \leq n-1$，$s \neq t$），分别表示顶点数、边数、期望的最短路径长度、起点和终点。

接下来 $m$ 行描述图中的边。第 $i$ 行包含三个整数 $u_i$、$v_i$、$w_i$（$0 \leq u_i, v_i \leq n-1$，$u_i \neq v_i$，$0 \leq w_i \leq 10^9$）。其中 $u_i$ 和 $v_i$ 表示该边的两个端点，$w_i$ 表示其权重。若 $w_i = 0$，则表示该边的权重已被擦除。

保证任意一对顶点之间至多存在一条边。

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.

如果无法按要求分配权重，则在唯一一行中输出 "NO"（不带引号）。

否则，在第一行输出 "YES"。接下来的 $m$ 行应包含最终图中的边，其中为原先被擦除权重的边重新分配了权重。第 $i$ 行应包含三个整数 $u_i$、$v_i$ 和 $w_i$，表示一条连接顶点 $u_i$ 与 $v_i$、权重为 $w_i$ 的边。新图的边集必须与输入图中的边集完全一致。原先未被擦除的边权必须保持不变；而新分配的权重可以是任意不超过 $10^{18}$ 的正整数。

输出中边的顺序无关紧要。顶点 $s$ 与 $t$ 之间的最短路径长度必须恰好等于 $L$。

若存在多种解法，输出任意一种即可。

Here's how the graph in the first sample case looks like :

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".

第一个样例中的图如下所示：

在第一个样例中，仅有一条边的权重缺失。将该边权重设为 8 后，从节点 0 到节点 4 的最短路径长度为 13。

在第二个样例中，图中仅含一条边。显然，唯一的方法是将缺失的权重替换为 123456789。

在最后一个样例中，没有需要赋值的边权，但此时最短路径长度与要求值不符，因此答案为 "NO"。