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 替换缺失的权重。
在最后一个示例中,没有要分配的权重,但最短路径的长度与所需的值不匹配,因此答案为“否”。