# 题目

## 题面

time limit per test：4 seconds

memory limit per test：256 megabytes

input：standard input

output：standard output

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 ≤ $10^9$,  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$ ≤ $10^9$). $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 $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.

# 思路

P.S.虽然Dijkstra的$O({nm})$的算法可以AC，但是那是在CF，考虑到时间问题，尽量写$O({nlogn})$的Dijkstra吧~

1. 将所有可决定边置为INF（大于给定的L即可）之后最短路依然小于L

2. 将所有可决定边置为1之后最短路依然大于L

# 代码

## 代码2

P.S.经过nike0good大佬的提醒，我们可以省去二分，在$O(1)$时间内求出P号边的权值