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?

The first line contains five integers $ n,m,L,s,t $ ( $ 2

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 $ 10^{18} $ . 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.

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