← 返回题目列表

Codeforces · 715/B

B. 完成图表

中文机器翻译题面 查看原题

ZS 编码器绘制了一个无向图,其中有 n 个顶点,编号从 0 到 n - 1,它们之间有 m 条边。图的每条边都被加权,每个权重都是一个正整数。

第二天,编码员 ZS 发现一些权重被删除了!所以他想为每条被删除权重的边重新分配正整数权重,使得结果图中顶点s和t之间的最短路径的长度恰好是L。你能帮助他吗?

输入

第一行包含五个整数 n, m, L, s, t (2 ≤ n ≤ 1000, 1 ≤ m ≤ 10 000, 1 ≤ L ≤ 109, 0 ≤ s, t ≤ n - 1, s ≠ t) — 顶点数、边数、最短路径所需长度、起始顶点和结束顶点分别。

然后,接下来是描述图形边缘的 m 条线。其中第 i 个包含三个整数 ui, vi, wi (0 ≤ ui, vi ≤ n - 1, ui ≠ vi, 0 ≤ wi ≤ 109)。 ui 和 vi 表示边的端点,wi 表示其权重。如果 wi 等于 0,则删除相应边的权重。

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

输出

如果无法以所需的方式分配权重,则在唯一的行中打印“NO”(不带引号)。

否则,在第一行打印“YES”。接下来的 m 行应包含结果图的边,并将权重分配给已删除权重的边。其中第 i 个应该包含三个整数 ui、vi 和 wi,表示权重 wi 的顶点 ui 和 vi 之间的边。新图的边必须与输入图中的边一致。未被删除的权重必须保持不变,而新的权重可以是不超过1018的任何正整数。

输出中边的顺序并不重要。 s 和 t 之间的最短路径的长度必须等于 L。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

5 5 13 0 4
0 1 5
2 1 2
3 2 3
1 4 0
4 3 4

输出 #1

YES
0 1 5
2 1 2
3 2 3
1 4 8
4 3 4

输入 #2

2 1 123456789 0 1
0 1 0

输出 #2

YES
0 1 123456789

输入 #3

2 1 999999999 1 0
0 1 1000000000

输出 #3

NO

注意

第一个示例案例中的图表如下所示:

在第一个示例案例中,仅缺少一个边权重。放置权重 8 给出了从 0 到 4、长度为 13 的最短路径。

在第二个示例案例中,只有一条边。显然,唯一的方法就是用 123456789 替换缺失的权重。

在最后一个示例中,没有要分配的权重,但最短路径的长度与所需的值不匹配,因此答案为“否”。