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 ≤ 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, ui, vi, wi (0 ≤ ui, vi ≤ n - 1, ui ≠ vi, 0 ≤ wi ≤ 109). ui and vi denote the endpoints of the edge and wi denotes its weight. If wi 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 ui, vi and wi, denoting an edge between vertices ui and vi of weight wi. 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.

Examples

Input

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


Output

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


Input

2 1 123456789 0 1
0 1 0


Output

YES
0 1 123456789


Input

2 1 999999999 1 0
0 1 1000000000


Output

NO

Note

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

<image>

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

Source: codeforces | Difficulty: HARD
Tags: Sorting

Graph algorithms

Shortest paths

Constructive algorithms


Solutions:
import heapq
from collections import defaultdict

class Graph:

	def __init__(self, n):
		self.nodes = set(range(n))
		self.edges = defaultdict(list)
		self.distances = {}

	def add_edge(self, from_node, to_node, distance):
		self.edges[from_node].append(to_node)
		self.edges[to_node].append(from_node)
		self.distances[from_node, to_node] = distance
		self.distances[to_node, from_node] = distance

def dijkstra(graph, initial, end):
	visited = {initial: 0}
	path = {}
	h = [(0, initial)]
	nodes = set(graph.nodes)
	while nodes and h:
		(current_weight, min_node) = heapq.heappop(h)
		try:
			while min_node not in nodes:
				(current_weight, min_node) = heapq.heappop(h)
		except IndexError:
			break
		if min_node == end:
			break
		nodes.remove(min_node)
		for v in graph.edges[min_node]:
			weight = current_weight + graph.distances[min_node, v]
			if v not in visited or weight < visited[v]:
				visited[v] = weight
				heapq.heappush(h, (weight, v))
				path[v] = min_node
	return (visited, path)
(n, m, L, s, t) = map(int, input().split())
min_g = Graph(n)
max_g = Graph(n)
g = Graph(n)
for _ in range(m):
	(u, v, w) = map(int, input().split())
	if w == 0:
		min_w = 1
		max_w = int(1e+18)
	else:
		min_w = max_w = w
	min_g.add_edge(u, v, min_w)
	max_g.add_edge(u, v, max_w)
	g.add_edge(u, v, w)
(min_ls, min_p) = dijkstra(min_g, s, t)
try:
	min_l = min_ls[t]
	max_l = dijkstra(max_g, s, t)[0][t]
except KeyError:
	min_l = 0
	max_l = -1
if min_l <= L <= max_l:
	while min_l < L:
		a = s
		b = z = t
		while z != s:
			if g.distances[z, min_p[z]] == 0:
				max_g.distances[z, min_p[z]] = min_g.distances[z, min_p[z]]
				max_g.distances[min_p[z], z] = min_g.distances[z, min_p[z]]
				a = z
				b = min_p[z]
			z = min_p[z]
		new_dist = min_g.distances[a, b] + L - min_l
		max_g.distances[a, b] = new_dist
		max_g.distances[b, a] = new_dist
		min_g = max_g
		(min_ls, min_p) = dijkstra(min_g, s, t)
		min_l = min_ls[t]
	if min_l == L:
		print('YES')
		print('\n'.join(('%s %s %s' % (u, v, w) for ((u, v), w) in min_g.distances.items() if u < v)))
	else:
		print('NO')
else:
	print('NO')


from collections import defaultdict
MAX_WEIGHT = 10 ** 14

def compute_path(graph, s, n):
	visited = [False] * n
	distances = [MAX_WEIGHT] * n
	ancestors = {}
	distances[s] = 0
	for i in range(n):
		(_, v) = min(((distances[j], j) for j in range(n) if not visited[j]))
		visited[v] = True
		for (to, length) in graph[v]:
			if distances[to] > distances[v] + length:
				distances[to] = distances[v] + length
				ancestors[to] = v
	return (ancestors, distances)

def output(graph, n_edges, extra, n, zeros, erased, leave):
	for i in range(n):
		for (to, length) in graph[i]:
			if to < i:
				if (i, to) in n_edges:
					print(i, to, n_edges[i, to])
				elif zeros and (i, to) in erased and ((i, to) not in leave):
					print(i, to, MAX_WEIGHT)
				else:
					print(i, to, length)
graph_with_0 = defaultdict(list)
graph_with_max = defaultdict(list)
(n, m, L, s, t) = map(int, input().split(' '))
erased = set()
for _ in range(m):
	(u, v, l) = map(int, input().split(' '))
	if l == 0:
		graph_with_0[u].append((v, 1))
		graph_with_0[v].append((u, 1))
		graph_with_max[u].append((v, MAX_WEIGHT))
		graph_with_max[v].append((u, MAX_WEIGHT))
		erased |= {(u, v), (v, u)}
	else:
		graph_with_0[u].append((v, l))
		graph_with_0[v].append((u, l))
		graph_with_max[u].append((v, l))
		graph_with_max[v].append((u, l))
(a1, d1) = compute_path(graph_with_0, s, n)
(a2, d2) = compute_path(graph_with_max, s, n)
if d2[t] < L:
	print('NO')
elif d2[t] == L:
	print('YES')
	output(graph_with_max, dict(), 0, n, False, erased, set())
elif d1[t] <= L:
	print('YES')
	v = t
	leave = set()
	n_edges = dict()
	total = 0
	while v != s:
		leave |= {(v, a1[v]), (a1[v], v)}
		if (v, a1[v]) in erased:
			cur = max(L - total - d2[a1[v]], 1)
			n_edges[max(v, a1[v]), min(v, a1[v])] = cur
			total += cur
		else:
			total += d1[v] - d1[a1[v]]
		v = a1[v]
	output(graph_with_0, n_edges, L - d1[t], n, True, erased, leave)
else:
	print('NO')


from collections import defaultdict
MAX = 10 ** 14

def Dijkstra(graph, s, n):
	visited = [False] * n
	d = [MAX] * n
	parents = {}
	d[s] = 0
	for i in range(n):
		(_, v) = min(((d[j], j) for j in range(n) if not visited[j]))
		visited[v] = True
		for (to, length) in graph[v]:
			if d[to] > d[v] + length:
				d[to] = d[v] + length
				parents[to] = v
	return (parents, d)

def PrintSol(graph, n_edges, n, zeros, edgesWithZero, leave):
	for i in range(n):
		for (to, length) in graph[i]:
			if to < i:
				if (i, to) in n_edges:
					print(i, to, n_edges[i, to])
				elif zeros and (i, to) in edgesWithZero and ((i, to) not in leave):
					print(i, to, MAX)
				else:
					print(i, to, length)
graphWithZero = defaultdict(list)
graphWithMax = defaultdict(list)
(n, m, L, s, t) = map(int, input().split(' '))
edgesWithZero = set()
for _ in range(m):
	(u, v, l) = map(int, input().split(' '))
	if l == 0:
		graphWithZero[u].append((v, 1))
		graphWithZero[v].append((u, 1))
		graphWithMax[u].append((v, MAX))
		graphWithMax[v].append((u, MAX))
		edgesWithZero |= {(u, v), (v, u)}
	else:
		graphWithZero[u].append((v, l))
		graphWithZero[v].append((u, l))
		graphWithMax[u].append((v, l))
		graphWithMax[v].append((u, l))
(a2, d2) = Dijkstra(graphWithMax, s, n)
(a1, d1) = Dijkstra(graphWithZero, s, n)
if d2[t] < L:
	print('NO')
elif d2[t] == L:
	print('YES')
	PrintSol(graphWithMax, dict(), n, False, edgesWithZero, set())
elif d1[t] <= L:
	print('YES')
	v = t
	leave = set()
	n_edges = dict()
	total = 0
	while v != s:
		leave |= {(v, a1[v]), (a1[v], v)}
		if (v, a1[v]) in edgesWithZero:
			cur = max(L - total - d2[a1[v]], 1)
			n_edges[max(v, a1[v]), min(v, a1[v])] = cur
			total += cur
		else:
			total += d1[v] - d1[a1[v]]
		v = a1[v]
	PrintSol(graphWithZero, n_edges, n, True, edgesWithZero, leave)
else:
	print('NO')