Jack has just moved to a new city called Rapture. He wants to use the public public transport system. The fare rules are as follows:  

1.Each pair of connected stations has a fare assigned to it regardless of direction of travel.  
2.If Jack travels from station A to station B, he only has to pay the  difference between (the fare from A to B) and (the cumulative fare paid to reach station A),  [fare(A,B) - total fare to reach station A].  If the difference is negative, travel is free of cost from A to B.  

Jack is low on cash and needs your help to figure out the most cost efficient way to go from the first station to the last station. Given the number of stations $g\text{_}nodes$ (numbered from $\mbox{1}$ to $g\text{_}nodes$), and the fares (weights) between the $g\text{_edges}$ pairs of stations that are connected, determine the lowest fare from station $\mbox{1}$ to station $g\text{_}nodes$.  

Example 

$g\text{_}nodes=4$ 

$g_{-}\textit{from}=[1,1,2,3]$ 

$g_{-}to=[2,3,4,4]$ 

$g\text{_weight}=[20,5,30,40]$   

The graph looks like this:

Travel from station $1\rightarrow2\rightarrow4$ costs $\textbf{20}$ for the first segment ($1\rightarrow2$) then the cost differential, an additional $30-20=10$ for the remainder.  The total cost is $30$.   

Travel from station $1\rightarrow3\rightarrow4$ costs $5$ for the first segment, then an additional $40-5=35$ for the remainder, a total cost of $\boldsymbol{40}$.   

The lower priced option costs $30$.  

Function Description 

Complete the getCost function in the editor below.  

getCost has the following parameters:

int g_nodes: the number of stations in the network  
int g_from[g_edges]: end stations of a bidirectional connection  
int g_to[g_edges]: $g\text{_from}[i]$ is connected to $g\textrm{_to}[i]$  at cost $g\text{_weight}[i]$  
int g_weight[g_edges]: the cost of travel between associated stations  

Prints 

- int or string: the cost of the lowest priced route from station $\mbox{I}$ to station $g\text{_}nodes$ or NO PATH EXISTS.  No return value is expected.

Input Format

The first line contains two space-separated integers, $g\text{_}nodes$ and $g\text{_edges}$, the number of stations and the number of connections between them. 

Each of the next $g\text{_edges}$ lines contains three space-separated integers, $g\text{_from},g\text{_to}$ and $g\text{_weight}$, the connected stations and the fare between them.  

Constraints

$1\leq g\text{_}nodes\leq50000$  
$1\leq g\text{_edges}\leq5000000$  
$1\leq g\text{_weight}[i]\leq10^7$

Source: hackerrank | Difficulty: MEDIUM
Tags: Graph algorithms


Solutions:
import heapq
(num_nodes, num_edges) = [int(i) for i in input().split()]
graph = {}
for i in range(1, num_nodes + 1):
	graph[i] = []
for _ in range(num_edges):
	(a, b, w) = [int(i) for i in input().split()]
	graph[a].append((w, b))
	graph[b].append((w, a))
queue = []
visited = set()
queue.append((0, 1))
no_path = True
while queue:
	curr = heapq.heappop(queue)
	visited.add(curr[1])
	if curr[1] == num_nodes:
		print(curr[0])
		no_path = False
		break
	for i in graph[curr[1]]:
		if i[1] not in visited:
			tmp = (max(curr[0], i[0]), i[1])
			heapq.heappush(queue, tmp)
if no_path:
	print('NO PATH EXISTS')


from heapq import *

def _get_input():
	return (int(i) for i in input().split())

def coneact(nodes, i, j, wieght):
	nodes[i].append((j, wieght))
(n, m) = _get_input()
nodes = [[] for i in range(n)]
for _ in range(m):
	(I, J, wieght) = _get_input()
	(I, J) = (I - 1, J - 1)
	coneact(nodes, I, J, wieght)
	coneact(nodes, J, I, wieght)
_max = 0
(color, acomplish) = (set(), False)
targets = [(0, 0)]
while not acomplish and len(targets) > 0:
	(_max, position) = heappop(targets)
	color.add(position)
	if position == n - 1:
		acomplish = True
		break
	for (node, wieght) in nodes[position]:
		if node not in color:
			rate = max(_max, wieght)
			heappush(targets, (rate, node))
if not acomplish:
	print('NO PATH EXISTS')
else:
	print(_max)


import queue

class Node:

	def __init__(self, name):
		self.name = name
		self.parent = None

	def join(self, other):
		my_leader = self.get_leader()
		other_leader = other.get_leader()
		if my_leader is other_leader:
			return
		other_leader.parent = my_leader

	def is_connected(self, other):
		my_leader = self.get_leader()
		other_leader = other.get_leader()
		if my_leader is not None and other_leader is not None:
			if my_leader is other_leader:
				return True
		return False

	def get_leader(self):
		parents = []
		curr = self
		while curr.parent is not None:
			parents.append(curr)
			curr = curr.parent
		for p in parents:
			p.parent = curr
		return curr

class Edge:

	def __init__(self, node1, node2, weight):
		self.node1 = node1
		self.node2 = node2
		self.weight = weight

	def __le__(self, other):
		return self.weight <= other.weight

	def __lt__(self, other):
		return self.weight < other.weight

	def __repr__(self):
		return repr((self.node1, self.node2, self.weight))
line = input().strip().split(' ')
n = int(line[0])
e = int(line[1])
nodes = []
for i in range(0, n + 1):
	nodes.append(Node(i))
edge_heap = queue.PriorityQueue()
max_fare = None
for i in range(0, e):
	line = input().strip().split(' ')
	n1 = int(line[0])
	n2 = int(line[1])
	fare = int(line[2])
	edge_heap.put(Edge(nodes[n1], nodes[n2], fare))
source = nodes[1]
sink = nodes[n]
max_edge = 0
while not edge_heap.empty():
	edge = edge_heap.get()
	edge.node1.join(edge.node2)
	max_edge = max(max_edge, edge.weight)
	if source.is_connected(sink):
		break
if source.is_connected(sink):
	print(max_edge)
else:
	print('NO PATH EXISTS')


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if not s1 in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if not s2 in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def dump_next_stations(graph, options, current, costs):
	if not current in graph:
		return
	for (station, cost) in graph[current]:
		base_cost = costs[current]
		new_cost = base_cost + max(0, cost - base_cost)
		if station in costs and costs[station] < new_cost:
			continue
		options.put((new_cost, station))

def calculate(graph, N):
	options = queue.PriorityQueue()
	costs = {1: 0}
	dump_next_stations(graph, options, 1, costs)
	while not options.empty():
		(cost, current) = options.get()
		if current == N:
			return cost
		if current in costs:
			continue
		costs[current] = cost
		dump_next_stations(graph, options, current, costs)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


import queue
import itertools
(n, e) = tuple(map(int, input().split()))
graph = [[] for _ in range(n)]
for _ in range(e):
	(n1, n2, cost) = tuple(map(int, input().split()))
	graph[n1 - 1].append((cost, n2 - 1))
	graph[n2 - 1].append((cost, n1 - 1))
result = -1
qq = queue.PriorityQueue()
qq.put((0, 0))
visited = list(itertools.repeat(False, n))
while not qq.empty():
	(cost, n1) = qq.get()
	if visited[n1]:
		continue
	visited[n1] = True
	if n1 == n - 1:
		result = cost
		break
	for (cost_n2, n2) in graph[n1]:
		if not visited[n2]:
			qq.put((max(cost_n2, cost), n2))
if result == -1:
	print('NO PATH EXISTS')
else:
	print(result)


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


from queue import PriorityQueue
(N, E) = map(int, input().split())
cost = {u: dict() for u in range(1, N + 1)}
for _ in range(E):
	(u, v, w) = map(int, input().split())
	cost[u][v] = w
	cost[v][u] = w
dist = [-1 for _ in range(N + 1)]
dist[1] = 0
que = PriorityQueue()
que.put((dist[1], 1))
while not que.empty():
	u = que.get()[1]
	if u == N:
		break
	for v in cost[u]:
		if dist[v] == -1 or dist[u] + max(0, cost[u][v] - dist[u]) < dist[v]:
			dist[v] = dist[u] + max(0, cost[u][v] - dist[u])
			que.put((dist[v], v))
if dist[N] != -1:
	print(dist[N])
else:
	print('NO PATH EXISTS')


def find(x):
	if p[x] != x:
		p[x] = find(p[x])
	return p[x]

def merge(x, y):
	x = find(x)
	y = find(y)
	if x != y:
		if c[x] > c[y]:
			p[y] = x
			c[x] += c[y]
		else:
			p[x] = y
			c[y] += c[x]
(n, m) = map(int, input().split())
p = list(range(n))
c = [1] * n
e = []
for _ in range(m):
	(x, y, r) = map(int, input().split())
	(x, y) = (x - 1, y - 1)
	if x > y:
		(x, y) = (y, x)
	e.append((r, x, y))
e = sorted(e)
i = 0
r = 0
while i < m and find(0) != find(n - 1):
	x = find(e[i][1])
	y = find(e[i][2])
	if x != y:
		merge(x, y)
		r = e[i][0]
	i += 1
if find(0) == find(n - 1):
	print(r)
else:
	print('NO PATH EXISTS')


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


from heapq import heappush, heappop

def dijkstra_mod(graph, weights, edges, S):
	weights[S] = 0
	seen = set()
	queue = [(weights[S], S)]
	while queue:
		(_, u) = heappop(queue)
		if u in seen:
			continue
		seen.add(u)
		for node in graph[u]:
			if (u, node) not in edges:
				continue
			edge = edges[u, node]
			if weights[node] == -1 or weights[node] > weights[u] + max(edge - weights[u], 0):
				weights[node] = weights[u] + max(edge - weights[u], 0)
			heappush(queue, (weights[node], node))
(N, E) = map(int, input().split())
graph = {k: [] for k in range(1, N + 1)}
weights = dict(zip(range(1, N + 1), [-1] * N))
edges = {}
for _ in range(E):
	(x, y, r) = map(int, input().split())
	graph[x].append(y)
	graph[y].append(x)
	edges[x, y] = min(edges.get((x, y), 10 ** 10), r)
	edges[y, x] = min(edges.get((x, y), 10 ** 10), r)
S = 1
weights[S] = 0
dijkstra_mod(graph, weights, edges, S)
res = weights[N] if weights[N] != -1 else 'NO PATH EXISTS'
print(res)


from heapq import heappush, heappop, heapify
(N, E) = tuple(map(int, input().split()))
ConnD = [[] for _ in range(N)]
NodeCost = [-1 for _ in range(N)]
for _ in range(E):
	(v1, v2, pairCost) = tuple(map(int, input().split()))
	(v1, v2) = (v1 - 1, v2 - 1)
	ConnD[v1].append((pairCost, v2))
	ConnD[v2].append((pairCost, v1))
curGraph = set([0])
curNeighbors = [(x[0], x[1], 0) for x in ConnD[0]]
NodeCost[0] = 0
heapify(curNeighbors)
while len(curNeighbors) > 0:
	(cost, vertex, origin) = heappop(curNeighbors)
	if vertex not in curGraph:
		curGraph.add(vertex)
		NodeCost[vertex] = cost
		for (pairCost, n) in ConnD[vertex]:
			if n not in curGraph:
				realCost = pairCost if pairCost > NodeCost[vertex] else NodeCost[vertex]
				heappush(curNeighbors, (realCost, n, vertex))
print(NodeCost[N - 1] if NodeCost[N - 1] > 0 else 'NO PATH EXISTS')


from heapq import *

def dijkstra(graph, dist, s):
	dist[s] = 0
	q = [(0, s)]
	while q:
		(d, u) = heappop(q)
		if d <= dist[u]:
			for (w, v) in graph[u]:
				diff = max(0, w - dist[u])
				if dist[v] > diff + dist[u]:
					dist[v] = diff + dist[u]
					heappush(q, (dist[v], v))
(N, M) = list(map(int, input().split()))
graph = [[] for i in range(N)]
for i in range(M):
	(u, v, w) = list(map(int, input().split()))
	graph[u - 1].append((w, v - 1))
	graph[v - 1].append((w, u - 1))
inf = 1 << 64 - 1
dist = [inf for i in range(N)]
dijkstra(graph, dist, 0)
if dist[N - 1] == inf:
	print('NO PATH EXISTS')
else:
	print(dist[N - 1])


from heapq import *

def dijkstra(source):
	pq = list()
	heappush(pq, (0, source))
	checked = {source}
	edge_to[source] = None
	while pq:
		(min_dist, current) = heappop(pq)
		if dist_to[current] == -1:
			dist_to[current] = min_dist
			for (weight, node) in adj_list[current]:
				if dist_to[node] == -1:
					if node not in checked:
						edge_to[node] = current
						checked.add(node)
					heappush(pq, (min_dist + max(0, weight - min_dist), node))
[n, m] = [int(x) for x in input().split()]
edge_to = [-1 for x in range(n + 1)]
dist_to = [-1 for x in range(n + 1)]
adj_list = [list() for x in range(n + 1)]
for i1 in range(m):
	[u, v, w] = [int(x) for x in input().split()]
	adj_list[u].append((w, v))
	adj_list[v].append((w, u))
dijkstra(1)
if dist_to[n] == -1:
	print('NO PATH EXISTS')
else:
	print(dist_to[n])


from heapq import heappop, heappush

def solve(G):
	N1 = len(G) - 1
	visited = set()
	stack = [(0, 0)]
	while stack:
		(c, n) = heappop(stack)
		visited.add(n)
		if n == N1:
			return c
		for v in filter(lambda v: v not in visited, G[n]):
			heappush(stack, (max(G[n][v], c), v))
	return None
(N, E) = map(int, input().split())
G = [{} for _ in range(N)]
for _ in range(E):
	(a, b, c) = map(int, input().split())
	G[a - 1][b - 1] = c
	G[b - 1][a - 1] = c
c = solve(G)
print(c if c != None else 'NO PATH EXISTS')


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


__author__ = 'Nathalie'
import sys
import queue

class G:

	def __init__(self, v, e):
		self.v = v
		self.e = e
		self.adj = [[] for x in range(v)]

	def add_edge(self, s, t, w):
		self.adj[s - 1].append((t - 1, w))

class KindOfDejkstra:

	def __init__(self, gr, s, t):
		self.gr = gr
		self.min_v_price = {}
		self.marked = {}
		self.start = s
		self.finish = t
		self.min_v_price[s] = 0
		self.marked[s] = False
		self.min_path = self.search()

	def search(self):
		q = queue.PriorityQueue()
		q.put((self.min_v_price[self.start], self.start))
		while not q.empty():
			(new_cur_v_price, cur_v_num) = q.get()
			for (next_v, weight) in self.gr.adj[cur_v_num]:
				if self.min_v_price.get(next_v, sys.maxsize) < weight:
					continue
				if not self.marked.get(next_v, False):
					self.min_v_price[next_v] = new_cur_v_price if weight < new_cur_v_price else weight
					q.put((self.min_v_price[next_v], next_v))
			self.marked[cur_v_num] = True
		return str(self.min_v_price.get(self.finish, 'NO PATH EXISTS'))
(n, e) = map(int, input().split())
gr = G(n, e)
for i in range(e):
	(s, t, w) = map(int, input().split())
	gr.add_edge(s, t, w)
	gr.add_edge(t, s, w)
print(KindOfDejkstra(gr, 0, n - 1).min_path)


from queue import PriorityQueue
(N, E) = map(int, input().split())
adj = [[] for _ in range(N)]
for _ in range(E):
	(A, B, C) = map(int, input().split())
	A -= 1
	B -= 1
	adj[A].append((B, C))
	adj[B].append((A, C))
dist = [0] * N
visited = [False] * N
queue = PriorityQueue()
queue.put((1, 0))
result = -1
while not queue.empty():
	(cur_dist, v) = queue.get()
	if v == N - 1:
		result = cur_dist - 1
		break
	if visited[v]:
		continue
	visited[v] = True
	for (n, r) in adj[v]:
		new_dist = cur_dist + max(r - cur_dist + 1, 0)
		if not 0 != dist[n] <= new_dist:
			dist[n] = new_dist
			if not visited[n]:
				queue.put((dist[n], n))
print('NO PATH EXISTS' if result == -1 else result)


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


from queue import PriorityQueue

def generate_problem():
	line = input().strip().split(' ')
	(num_nodes, num_edges) = (int(line[0]), int(line[1]))
	graph = {i: [] for i in range(1, num_nodes + 1)}
	for i in range(num_edges):
		line = input().strip().split(' ')
		(s, t, c) = (int(line[0]), int(line[1]), int(line[2]))
		graph[s].append((t, c))
		graph[t].append((s, c))
	return graph

def solve_problem(g):
	costs = ['pad'] + len(g) * [-1]
	costs[1] = 0
	queue = PriorityQueue()
	queue.put((0, 1))
	while not queue.empty():
		(cost, node) = queue.get()
		for (neighbor, edge_cost) in g[node]:
			new_cost = max(edge_cost, costs[node])
			if costs[neighbor] == -1 or costs[neighbor] > new_cost:
				costs[neighbor] = new_cost
				queue.put((new_cost, neighbor))
	return costs[-1] if costs[-1] != -1 else 'NO PATH EXISTS'
g = generate_problem()
print(solve_problem(g))


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


import heapq
import sys
infinity = int(1e+50)
(n, e) = tuple((int(x) for x in sys.stdin.readline().split()))
edges = tuple(([] for i in range(n)))
fares = [infinity] * n
for i in range(e):
	(s1, s2, fare) = tuple((int(x) for x in sys.stdin.readline().split()))
	s1 -= 1
	s2 -= 1
	edges[s1].append((s2, fare))
	edges[s2].append((s1, fare))
fares[0] = 0
todo = []
heapq.heappush(todo, (0, 0))
while len(todo) > 0:
	(fare, s) = heapq.heappop(todo)
	if fare > fares[s]:
		continue
	for (next_s, extra_fare) in edges[s]:
		next_fare = max(fare, extra_fare)
		if next_fare < fares[next_s]:
			fares[next_s] = next_fare
			heapq.heappush(todo, (next_fare, next_s))
if fares[n - 1] != infinity:
	print(fares[n - 1])
else:
	print('NO PATH EXISTS')


def heappush(heap, token):
	index = len(heap)
	heap.append(token)
	while index > 0 and token[1] < heap[(index - 1) // 2][1]:
		(heap[index], heap[(index - 1) // 2]) = (heap[(index - 1) // 2], heap[index])
		index = (index - 1) // 2

def heappop(heap):
	value = heap[0]
	if len(heap) == 1:
		return heap.pop(0)
	heap[0] = heap.pop(-1)
	index = 0
	while 2 * index + 1 < len(heap):
		if 2 * index + 2 < len(heap) and heap[index][1] > min(heap[2 * index + 1][1], heap[2 * index + 2][1]):
			offset = 1 if heap[2 * index + 1][1] < heap[2 * index + 2][1] else 2
			(heap[index], heap[2 * index + offset]) = (heap[2 * index + offset], heap[index])
			index = 2 * index + offset
		elif 2 * index + 2 == len(heap) and heap[index][1] > heap[2 * index + 1][1]:
			(heap[index], heap[2 * index + 1]) = (heap[2 * index + 1], heap[index])
		else:
			break
	return value
(V, E) = input().strip().split(' ')
(V, E) = [int(V), int(E)]
adj_list = [[] for _ in range(V)]
for _ in range(E):
	(a, b, c) = input().strip().split(' ')
	(a, b, c) = [int(a) - 1, int(b) - 1, int(c)]
	adj_list[a].append((b, c))
	adj_list[b].append((a, c))
cost_to = [-1] * V
visited = [False] * V
heap = [(0, 0)]
while heap != []:
	(current, cost_so_far) = heappop(heap)
	if visited[current] == False:
		visited[current] = True
		if current == V - 1:
			cost_to[V - 1] = cost_so_far
			break
		for (neighbor, edge_weight) in adj_list[current]:
			if cost_to[neighbor] == -1 or max(cost_so_far, edge_weight) < cost_to[neighbor]:
				cost_to[neighbor] = max(cost_so_far, edge_weight)
				heappush(heap, (neighbor, cost_to[neighbor]))
print('NO PATH EXISTS' if cost_to[V - 1] == -1 else cost_to[V - 1])


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


import heapq
(N, E) = map(int, input().split())
G = [[] for i in range(N + 1)]
for e in range(E):
	(A, B, C) = map(int, input().split())
	G[A].append((B, C))
	G[B].append((A, C))
active = [(0, 1)]
out = 'NO PATH EXISTS'
visited = [False] * (N + 1)
while len(active):
	(c, i) = heapq.heappop(active)
	if visited[i]:
		continue
	visited[i] = True
	if i == N:
		out = c
		break
	for (j, d) in G[i]:
		if not visited[j]:
			heapq.heappush(active, (max(c, d), j))
print(out)


from queue import PriorityQueue
from sys import stderr

class Vertex:

	def __init__(self):
		self.succ = []
		self.cost = -1

	def addSucc(self, ind, cost):
		self.succ.append((ind, cost))

	def __lt__(self, other):
		return False
(nv, ne) = map(int, input().split())
graph = [Vertex() for i in range(nv)]
for i in range(ne):
	(a, b, c) = map(int, input().split())
	graph[a - 1].addSucc(b - 1, c)
	graph[b - 1].addSucc(a - 1, c)
q = PriorityQueue()
v = graph[0]
q.put((0, v))
while not q.empty():
	(c, v) = q.get()
	if v.cost < 0:
		v.cost = c
	else:
		continue
	if v is graph[-1]:
		break
	for (isu, sc) in v.succ:
		s = graph[isu]
		nc = max(sc, c)
		if s.cost < 0 or nc < s.cost:
			q.put((nc, s))
c = graph[-1].cost
if c < 0:
	print('NO PATH EXISTS')
else:
	print(c)


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


maxf = 100000000
import sys
sys.setrecursionlimit(50000)

class Station:

	def __init__(self, no):
		self.no = no
		self.parent = None
		self.arretes = []

	def find(self):
		if self.parent == None:
			return self
		return self.parent.find()

	def find2(self):
		if self.parent == None:
			return self
		elif self.parent != self:
			self.parent = self.parent.find2()
		return self.parent

	def __str__(self):
		return '(%s, %s)' % (self.no, ' | '.join(map(lambda a: '%s %s %s' % (a.s1.no, a.s2.no, a.fare), self.arretes)))

class Arrete:

	def __init__(self, fare, s1, s2):
		self.fare = fare
		self.s1 = s1
		self.s2 = s2

	def __str__(self):
		return 's1 : %s, s2 : %s, fare : %s' % (self.s1.no, self.s2.no, self.fare)

def union(x, y):
	xRacine = x.find2()
	yRacine = y.find2()
	if xRacine != yRacine:
		xRacine.parent = yRacine

def findBestPath(prevStations, station, endStation):
	f = maxf
	for a in station.arretes:
		currentStation = a.s1
		destStation = a.s2
		if station != currentStation:
			currentStation = a.s2
			destStation = a.s1
		if destStation in prevStations:
			continue
		if destStation == endStation:
			return min(f, a.fare)
		else:
			tmpf = findBestPath(prevStations + [currentStation], destStation, endStation)
			if tmpf < maxf:
				f = min(f, max(a.fare, tmpf))
	return f
(N, E) = map(int, input().strip().split())
stations = {}
arretes = {}
for _ in range(E):
	(o, d, f) = map(int, input().strip().split())
	if o not in stations:
		stations[o] = Station(o)
	if d not in stations:
		stations[d] = Station(d)
	if f not in arretes:
		arretes[f] = [Arrete(f, stations[o], stations[d])]
	else:
		arretes[f].append(Arrete(f, stations[o], stations[d]))
if N not in stations or 1 not in stations:
	print('NO PATH EXISTS')
	exit(0)
t = sorted(arretes)
for key in t:
	for arrete in arretes[key]:
		if arrete.s1.find2() != arrete.s2.find2():
			arrete.s1.arretes.append(arrete)
			arrete.s2.arretes.append(arrete)
			union(arrete.s1, arrete.s2)
prevStations = []
f = findBestPath(prevStations, stations[1], stations[N])
print(f if f != maxf else 'NO PATH EXISTS')


import heapq
INF = 1000000000

def foo(N, E, w):
	dist = [INF] * (N + 1)
	dist[1] = 0
	Q = [(0, 1)]
	seen = set()
	while len(Q) > 0:
		(cost, v) = heapq.heappop(Q)
		seen.add(v)
		for u in w[v]:
			if not u in seen:
				val = max(dist[v], w[u][v])
				if dist[u] > val:
					dist[u] = val
					heapq.heappush(Q, (dist[u], u))
	return dist[N]
(N, E) = list(map(int, input().split()))
w = {}
for i in range(E):
	(x, y, c) = list(map(int, input().split()))
	if not x in w:
		w[x] = {}
	w[x][y] = c
	if not y in w:
		w[y] = {}
	w[y][x] = c
res = foo(N, E, w)
if res == INF:
	print('NO PATH EXISTS')
else:
	print(res)


import queue

class Node:

	def __init__(self, index):
		self.index = index
		self.edges = {}

class Graph:

	def __init__(self, size):
		self.size = size
		self.nodes = [None] * (size + 1)
		for i in range(size):
			self.nodes[i + 1] = Node(i + 1)

def dijkstra(startIndex, g):
	distances = []
	visited = []
	for i in range(g.size + 1):
		distances.append(float('inf'))
		visited.append(False)
	distances[startIndex] = 0
	q = queue.PriorityQueue()
	atIndex = startIndex
	while atIndex != -1:
		at = g.nodes[atIndex]
		for edge in at.edges:
			weight = max(0, at.edges[edge] - distances[atIndex])
			if visited[edge] == True:
				continue
			dist = weight + distances[atIndex]
			distances[edge] = min(dist, distances[edge])
			q.put([distances[edge], edge])
		visited[atIndex] = True
		atIndex = -1
		while not q.empty():
			temp = q.get()
			if visited[temp[1]] == False:
				atIndex = temp[1]
				break
	return distances
(n, e) = (int(x) for x in input().split())
g = Graph(n)
for i in range(e):
	(start, end, weight) = (int(x) for x in input().split())
	g.nodes[start].edges[end] = weight
	g.nodes[end].edges[start] = weight
distances = dijkstra(1, g)
if distances[n] == float('inf'):
	print('NO PATH EXISTS')
else:
	print(distances[n])


class Node:

	def __init__(self, i):
		self.i = i
		self.next = self
		self.c = 1

	def find(self):
		if self.next == self:
			return self
		else:
			return self.next.find()

	def union(self, other):
		other_top = other.find()
		self_top = self.find()
		if other_top.i == self_top.i:
			return
		if self_top.c > other_top.c:
			other.union(self)
			return
		self_top.next = other_top
		other_top.c += self_top.c

class Unioner:

	def __init__(self, n):
		self.n = n
		self.m = {}
		for i in range(n):
			self.m[i] = Node(i)

	def union(self, a, b):
		self.m[a].union(self.m[b])

	def find(self, a):
		return self.m[a].find()

def minPath(edges, n):
	edges.sort(key=lambda x: x[2])
	unioner = Unioner(n + 1)
	for e in edges:
		unioner.union(e[0], e[1])
		if unioner.find(1) == unioner.find(n):
			return e[2]
	return 'NO PATH EXISTS '
(n, e) = input().split()
edges = []
for l in range(int(e)):
	(a, b, c) = input().split()
	edges.append((int(a), int(b), int(c)))
res = minPath(edges, int(n))
print(res)


from operator import itemgetter
(n, e) = [int(x) for x in input().split()]
parts = list(range(n))
edges = []
for _ in range(e):
	edge = [int(x) for x in input().split()]
	if edge[0] > edge[1]:
		(edge[0], edge[1]) = (edge[1], edge[0])
	edges.append([edge[0] - 1, edge[1] - 1, edge[2]])
edges = sorted(edges, key=itemgetter(2))

def comp(l):
	while parts[l] != l:
		l = parts[l]
	return l
ans = None
for edge in edges:
	pi = comp(edge[0])
	pj = comp(edge[1])
	if pi < pj:
		parts[edge[1]] = pi
		parts[pj] = pi
	elif pj < pi:
		parts[edge[0]] = pj
		parts[pi] = pj
	pn = comp(n - 1)
	if pn == 0:
		ans = edge[2]
		break
	else:
		parts[-1] = pn
print(ans if ans else 'NO PATH EXISTS')


def resol2():
	from collections import deque
	(n, e) = [int(x) for x in input().split()]
	nodes = [[] for x in range(n + 1)]
	costs = [None] * (n + 1)
	for ee in range(e):
		(a, b, cost) = [int(x) for x in input().split()]
		nodes[a].append((b, cost))
		nodes[b].append((a, cost))
	for node in nodes:
		sorted(node, key=lambda l: l[1])
	pendents = deque([(1, 0)])
	costs[1] = 0
	while len(pendents) > 0:
		(idactual, cost) = pendents.pop()
		actual = nodes[idactual]
		costactual = costs[idactual]
		if costactual < cost:
			continue
		for linia in actual:
			idveinat = linia[0]
			difcost = max(0, linia[1] - costactual)
			noucost = costactual + difcost
			costveinat = costs[idveinat]
			if costveinat is None or noucost < costveinat:
				costs[idveinat] = noucost
				if difcost == 0:
					pendents.append((idveinat, noucost))
				else:
					pendents.appendleft((idveinat, noucost))
	if costs[n] is None:
		return 'NO PATH EXISTS'
	else:
		return costs[n]
print(resol2())


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


from datetime import datetime
from os.path import os

class DisjointSetNode:

	def __init__(self, data):
		self.data = data
		self.parent = None
		self.rank = 0

	def setParent(self, parentNode):
		self.parent = parentNode

	def getParent(self):
		return self.parent

	def getData(self):
		return self.data

	def getRank(self):
		return self.rank

	def __eq__(self, other):
		return self.data == other.data

class DisjointSet:

	def __init__(self):
		self.disjointSetNodeMap = {}

	def getParent(self, data):
		if data in self.disjointSetNodeMap:
			return self.disjointSetNodeMap[data].getParent()
		else:
			return None

	def makeSet(self, data):
		node = DisjointSetNode(data)
		node.setParent(node)
		self.disjointSetNodeMap[data] = node

	def union(self, data1, data2):
		parent1 = self.findSet(data1)
		parent2 = self.findSet(data2)
		if parent1 == parent2:
			return False
		if parent1.getRank() >= parent2.getRank():
			if parent1.getRank() == parent2.getRank():
				parent1.rank += 1
			parent2.parent = parent1
		else:
			parent1.parent = parent2
		return True

	def findSet(self, data):
		disjointSetNode = self.disjointSetNodeMap[data]
		if disjointSetNode.getParent() == disjointSetNode:
			return disjointSetNode
		disjointSetNode.parent = self.findSet(disjointSetNode.getParent().getData())
		return disjointSetNode.parent

class Edge:

	def __init__(self, fromVertex, toVertex, name=None, weight=0):
		self.fromVertex = fromVertex
		self.toVertex = toVertex
		self.name = name
		self.weight = weight

	def __gt__(self, other):
		return self.weight > other.weight

	def __ge__(self, other):
		return self.weight >= other.weight

	def __lt__(self, other):
		return self.weight < other.weight

	def __le__(self, other):
		return self.weight <= other.weight

	def __eq__(self, other):
		return self.fromVertex == other.getFromVertex() and self.toVertex == other.getToVertex()

	def __str__(self):
		return 'Edge With Starting Vertex : ' + str(self.fromVertex) + ', End Vertex : ' + str(self.toVertex) + ', Name : ' + str(self.name) + ' And Weight : ' + str(self.weight)

	def __hash__(self):
		return hash(self.name)

	def getFromVertex(self):
		return self.fromVertex

	def getToVertex(self):
		return self.toVertex

	def getName(self):
		return self.name

	def getWeight(self):
		return self.weight

	def setWeight(self, weight):
		self.weight = weight

class UnDirectedGraph:

	def __init__(self, vertexCount, edgeCount):
		self.vertexCount = vertexCount
		self.edgeCount = edgeCount
		self.edgeList = []

class MinimumSpanningTree:

	def helperFunction(self, mstEdgeMap, startVertex, destinationVertex, visitedVertexMap, currentCost):
		visitedVertexMap[startVertex] = True
		if startVertex == destinationVertex:
			return (True, currentCost)
		ll = mstEdgeMap[startVertex]
		for tempTuple in ll:
			if tempTuple[0] in visitedVertexMap and visitedVertexMap[tempTuple[0]]:
				continue
			tempCost = currentCost if currentCost > tempTuple[1] else tempTuple[1]
			(isValid, cost) = self.helperFunction(mstEdgeMap, tempTuple[0], destinationVertex, visitedVertexMap, tempCost)
			if isValid:
				return (isValid, cost)
			else:
				continue
		visitedVertexMap[startVertex] = False
		return (False, currentCost)

	def kruskalsAlgo(self, graph):
		sortedEdgeList = []
		disjointSet = DisjointSet()
		mstEdgeMap = {}
		for value in graph.edgeList:
			sortedEdgeList.append(value)
		sortedEdgeList = sorted(sortedEdgeList, key=lambda edge: edge.getWeight())
		vertexCount = graph.vertexCount + 1
		for iLoop in range(1, vertexCount):
			disjointSet.makeSet(iLoop)
		for edge in sortedEdgeList:
			if disjointSet.union(edge.getFromVertex(), edge.getToVertex()):
				if edge.getFromVertex() not in mstEdgeMap:
					mstEdgeMap[edge.getFromVertex()] = []
				if edge.getToVertex() not in mstEdgeMap:
					mstEdgeMap[edge.getToVertex()] = []
				mstEdgeMap[edge.getFromVertex()].append((edge.getToVertex(), edge.getWeight()))
				mstEdgeMap[edge.getToVertex()].append((edge.getFromVertex(), edge.getWeight()))
		visitedVertexMap = {}
		return self.helperFunction(mstEdgeMap, 1, graph.vertexCount, visitedVertexMap, 0)
(vertexCount, edgeCount) = input().split(' ')
(vertexCount, edgeCount) = (int(vertexCount), int(edgeCount))
g = UnDirectedGraph(vertexCount, edgeCount)
for iLoop in range(edgeCount):
	(sVertex, eVertex, edgeWeight) = input().strip().split(' ')
	g.edgeList.append(Edge(int(sVertex), int(eVertex), 'E' + str(iLoop), int(edgeWeight)))
mst = MinimumSpanningTree()
(isValid, cost) = mst.kruskalsAlgo(g)
if isValid:
	print(cost)
else:
	print('NO PATH EXISTS')


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


from collections import defaultdict
from heapq import heappush, heappop

def compute_min(n, costmap, links):
	min_cost = {}
	to_visit = []
	heappush(to_visit, (0, 1))
	while len(to_visit) > 0:
		(cost, station_a) = heappop(to_visit)
		for station_b in links[station_a]:
			cost_to_station_b = max(cost, costmap[station_a, station_b])
			if station_b not in min_cost or cost_to_station_b < min_cost[station_b]:
				min_cost[station_b] = cost_to_station_b
				heappush(to_visit, (cost_to_station_b, station_b))
	if n in min_cost:
		return min_cost[n]
	else:
		return None
costmap = {}
links = defaultdict(set)
(n, e) = list(map(int, input().split()))
for i in range(e):
	(a, b, cost) = list(map(int, input().split()))
	costmap[a, b] = cost
	costmap[b, a] = cost
	links[a].add(b)
	links[b].add(a)
cost = compute_min(n, costmap, links)
print(cost if cost is not None else 'NO PATH EXISTS')


from queue import PriorityQueue
[n, e] = [int(i) for i in input().split(' ')]
m = {i: {} for i in range(1, n + 1)}
for _ in range(e):
	[n1, n2, w] = [int(i) for i in input().strip().split(' ')]
	m[n1][n2] = w
	m[n2][n1] = w
pq = PriorityQueue()
for i in m[1]:
	pq.put((m[1][i], i))
traversed = {1}
while not pq.empty():
	(w, this_node) = pq.get()
	if this_node == n:
		print(w)
		break
	for i in m[this_node]:
		if i not in traversed:
			pq.put((w + (m[this_node][i] - w if m[this_node][i] > w else 0), i))
	traversed.add(this_node)
if pq.empty():
	print('NO PATH EXISTS')


from heapq import *
(N, E) = map(int, input().split(' '))
adj = [[] for _n_ in range(N)]
for edge in range(E):
	(a, b, c) = map(int, input().strip().split(' '))
	adj[b - 1].append((a - 1, c))
	adj[a - 1].append((b - 1, c))
oo = 1000000000000000000
mark = [oo for _n_ in range(N)]
queue = [(0, 0)]
while len(queue) > 0:
	(cost_a, a) = heappop(queue)
	if mark[a] < oo:
		continue
	mark[a] = cost_a
	for (b, cost_b) in adj[a]:
		if mark[b] < oo:
			continue
		heappush(queue, (max(mark[a], cost_b), b))
print(mark[N - 1] if mark[N - 1] < oo else 'NO PATH EXISTS')


class Heap(object):

	class Item(object):

		def __init__(self, val, pos=0):
			self.val = val
			self.pos = pos

	def __init__(self, cmp, size=1):
		self.data = [None for i in range(size + 1)]
		self.count = 0
		self.cmp_val = cmp
		self.cmp = lambda x, y: self.cmp_val(x.val, y.val)

	def __len__(self):
		return self.count

	def construct(self, arr):
		self.data = [None] + [Heap.Item(arr[i], i + 1) for i in range(len(arr))]
		self.count = len(arr)
		return [self.data[i] for i in range(1, self.count + 1)]

	def peek(self):
		return self.data[1].val

	def extract(self):
		item = self.data[1]
		self.data[1] = self.data[self.count]
		self.data[1].pos = 1
		self.data[self.count] = None
		self.count -= 1
		self.__down(1)
		item.pos = 0
		return item.val

	def insert(self, x):
		self.count += 1
		item = Heap.Item(x, self.count)
		if self.count == len(self.data):
			self.data.append(item)
		else:
			self.data[self.count] = item
		self.__up(item.pos)
		return item

	def update(self, item, new_value):
		old_value = item.val
		item.val = new_value
		if self.cmp_val(new_value, old_value):
			self.__up(item.pos)
		else:
			self.__down(item.pos)

	def __up(self, n):
		while n > 1:
			i = n // 2
			if self.cmp(self.data[i], self.data[n]):
				break
			(self.data[i], self.data[n]) = (self.data[n], self.data[i])
			(self.data[i].pos, self.data[n].pos) = (i, n)
			n = i

	def __down(self, i):
		n = 2 * i
		while n <= self.count:
			if self.cmp(self.data[i], self.data[n]) and (n + 1 > self.count or self.cmp(self.data[i], self.data[n + 1])):
				break
			if n + 1 <= self.count and self.cmp(self.data[n + 1], self.data[n]):
				n = n + 1
			(self.data[i], self.data[n]) = (self.data[n], self.data[i])
			(self.data[i].pos, self.data[n].pos) = (i, n)
			i = n
			n = 2 * i
inf = 10 ** 8
(N, E) = [int(x) for x in input().strip().split(' ')]
G = [[] for i in range(N)]
for _ in range(E):
	(u, v, w) = input().strip().split(' ')
	(u, v, w) = [int(u) - 1, int(v) - 1, int(w)]
	G[u].append((v, w))
	G[v].append((u, w))
heap = Heap(lambda x, y: x < y, 0)
items = heap.construct([(inf, i) for i in range(N)])
heap.update(items[0], (0, 0))
while len(heap) > 0:
	(fu, u) = heap.extract()
	if u == N - 1:
		break
	for (v, w) in G[u]:
		(fv, v) = items[v].val
		fuv = max(fu, w)
		if fuv < fv:
			heap.update(items[v], (fuv, v))
if items[N - 1].val[0] == 10 ** 8:
	print('NO PATH EXISTS')
else:
	print(items[N - 1].val[0])


import sys
import queue

def next_node(current, matrix, queue, tempcost):
	for (station, cost) in matrix[current]:
		base_cost = tempcost[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in tempcost and tempcost[station] < cost:
			continue
		queue.put((cost, station))

def main():
	(N, E) = [int(x) for x in sys.stdin.readline().split()]
	matrix = {}
	while E > 0:
		(n1, n2, cost) = [int(x) for x in sys.stdin.readline().split()]
		if n1 not in matrix:
			matrix[n1] = []
		matrix[n1].append((n2, cost))
		if n2 not in matrix:
			matrix[n2] = []
		matrix[n2].append((n1, cost))
		E = E - 1
	tempcost = {1: 0}
	queue_data = queue.PriorityQueue()
	next_node(1, matrix, queue_data, tempcost)
	while not queue_data.empty():
		(cost, current) = queue_data.get()
		if current == N:
			print(cost)
			sys.exit()
		if current in tempcost:
			continue
		tempcost[current] = cost
		next_node(current, matrix, queue_data, tempcost)
	if current != N:
		print('NO PATH EXISTS')
main()


from collections import defaultdict
from heapq import *

def dijkstra(matrix):
	maxes = defaultdict(lambda : None)
	Q = []
	maxes[1] = 0
	Q.append((0, 1))
	seen = set()
	while Q:
		(src_charge, src_v) = heappop(Q)
		if src_v in seen:
			continue
		maxes[src_v] = src_charge
		seen.add(src_v)
		for (dest_v, dest_charge) in list(iter(matrix[src_v].items())):
			if dest_v in seen:
				continue
			if not maxes[dest_v] or maxes[dest_v] > max(src_charge, dest_charge):
				new_charge = max(src_charge, dest_charge)
				maxes[dest_v] = new_charge
				heappush(Q, (new_charge, dest_v))
	return maxes
(N, M) = [int(num) for num in input().split(' ')]
matrix = defaultdict(lambda : defaultdict(lambda : None))
for idx in range(M):
	(i, j, c) = [int(num) for num in input().strip().split(' ')]
	(matrix[i][j], matrix[j][i]) = (c, c)
maxes = dijkstra(matrix)
print(maxes[N] if maxes[N] else 'NO PATH EXISTS')


def get_class(c, v):
	p = v
	pp = c[p]
	while True:
		ppp = c[pp]
		if pp == ppp:
			return pp
		c[p] = ppp
		p = pp
		pp = ppp

def add_edge(c, v1, v2):
	class1 = get_class(c, v1)
	class2 = get_class(c, v2)
	if class1 < class2:
		c[class2] = class1
	if class2 < class1:
		c[class1] = class2
(num_city, num_edges) = (int(x) for x in input().split())
e = []
for i in range(num_edges):
	(v1, v2, cost) = (int(x) for x in input().split())
	e.append((cost, v1 - 1, v2 - 1))
e = sorted(e)
c = [i for i in range(num_city)]
rv = -1
for (cost, v1, v2) in e:
	add_edge(c, v1, v2)
	if get_class(c, num_city - 1) == 0:
		rv = cost
		break
if rv == -1:
	print('NO PATH EXISTS')
else:
	print(rv)


import sys
from heapq import heappush, heappop
import time
probleminimumfo = input().strip()
(N, E) = probleminimumfo.split(' ')
N = int(N)
E = int(E)

def calculmiddle(number, updated, middle):
	queue = []
	rest = list(middle[number] - start)
	updated.update(middle[number])
	queue += rest
	while queue != []:
		rest = list(middle[queue[0]] - updated)
		updated.update(middle[queue[0]])
		queue += rest
		del queue[0]

def isThereRoute2(start, end, middle, new):
	if new[1] in start and new[2] in end:
		return True
	elif new[2] in start and new[1] in end:
		return True
	if new[1] in start:
		start.add(new[2])
		if new[2] in middle:
			calculmiddle(new[2], start, middle)
	elif new[2] in start:
		start.add(new[1])
		if new[1] in middle:
			calculmiddle(new[1], start, middle)
	elif new[1] in end:
		end.add(new[2])
		if new[2] in middle:
			calculmiddle(new[2], end, middle)
	elif new[2] in end:
		end.add(new[1])
		if new[1] in middle:
			calculmiddle(new[1], end, middle)
	else:
		if new[1] in middle:
			middle[new[1]].add(new[2])
		else:
			middle[new[1]] = set([new[2]])
		if new[2] in middle:
			middle[new[2]].add(new[1])
		else:
			middle[new[2]] = set([new[1]])
	return False
costs = []
for x in range(E):
	(A, B, fee) = input().strip().split(' ')
	A = int(A)
	B = int(B)
	fee = int(fee)
	heappush(costs, (fee, A - 1, B - 1))
efficient = 10000001
start = set([0])
end = set([N - 1])
middle = {}
while costs != []:
	x = heappop(costs)
	if isThereRoute2(start, end, middle, x):
		efficient = x[0]
		break
if efficient == 10000001:
	print('NO PATH EXISTS')
else:
	print(efficient)


(n, e) = map(int, input().strip().split())
parent = [-1] * n

def find(n):
	if parent[n] < 0:
		return n
	pt = find(parent[n])
	parent[n] = pt
	return pt
edges = []
for ee in range(e):
	(a, b, c) = map(int, input().strip().split())
	a -= 1
	b -= 1
	edges.append((c, a, b))
edges.sort()
if find(0) == find(n - 1):
	print(0)
else:
	for (c, a, b) in edges:
		a = find(a)
		b = find(b)
		if a != b:
			if parent[a] == parent[b]:
				parent[b] -= 1
			if parent[a] > parent[b]:
				parent[a] = b
			else:
				parent[b] = a
		if find(0) == find(n - 1):
			print(c)
			break
	else:
		print('NO PATH EXISTS')


import heapq
(n, e) = [int(x) for x in input().split()]
g = {}
dist = [float('inf') for x in range(n + 2)]
for _ in range(e):
	i = [int(x) for x in input().split()]
	if i[0] not in g:
		g[i[0]] = []
	if i[1] not in g:
		g[i[1]] = []
	g[i[0]].append((i[1], i[2]))
	g[i[1]].append((i[0], i[2]))
visited = set([])
queue = []
heapq.heappush(queue, (0, 1))
while queue:
	(cost, node) = heapq.heappop(queue)
	if node in visited:
		continue
	visited.add(node)
	dist[node] = cost
	for x in g[node]:
		if x[0] not in visited:
			newcost = max(cost, x[1])
			heapq.heappush(queue, (newcost, x[0]))
print(dist[n] if dist[n] < float('inf') else 'NO PATH EXISTS')


import sys
import queue

def next_node(current, matrix, queue, tempcost):
	for (station, cost) in matrix[current]:
		base_cost = tempcost[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in tempcost and tempcost[station] < cost:
			continue
		queue.put((cost, station))

def main():
	(N, E) = map(int, input().split())
	matrix = {}
	while E > 0:
		(n1, n2, cost) = map(int, input().split())
		if n1 not in matrix:
			matrix[n1] = []
		matrix[n1].append((n2, cost))
		if n2 not in matrix:
			matrix[n2] = []
		matrix[n2].append((n1, cost))
		E = E - 1
	tempcost = {1: 0}
	queue_data = queue.PriorityQueue()
	next_node(1, matrix, queue_data, tempcost)
	while not queue_data.empty():
		(cost, current) = queue_data.get()
		if current == N:
			print(cost)
			sys.exit()
		if current in tempcost:
			continue
		tempcost[current] = cost
		next_node(current, matrix, queue_data, tempcost)
	if current != N:
		print('NO PATH EXISTS')
main()


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


def bfs(mst, src):
	q = [src]
	parent = [None for _ in range(n)]
	state = [-1 for _ in range(n)]
	state[src] = 2
	while q:
		u = q.pop()
		for (v, w) in mst[u]:
			if state[v] == -1:
				state[v] = 2
				parent[v] = (u, w)
				q.insert(0, v)
			if v == n - 1:
				return (parent, True)
		state[u] = 1
	return (parent, False)

def find(a, nodes):
	if nodes[a][1] == a:
		return a
	else:
		return find(nodes[a][1], nodes)

def union(a, b, nodes):
	r1 = find(a, nodes)
	r2 = find(b, nodes)
	if r1 == r2:
		return nodes
	elif nodes[r1][0] > nodes[r2][0]:
		nodes[r2][1] = r1
	elif nodes[r1][0] < nodes[r2][0]:
		nodes[r1][1] = r2
	else:
		nodes[r2][1] = r1
		nodes[r1][0] += 1
	return nodes
(n, m) = [int(i) for i in input().split()]
nodes = {}
for i in range(n):
	nodes[i] = [0, i]
edges = []
for _ in range(m):
	(a, b, w) = [int(i) for i in input().split()]
	edges.append((a, b, w))
edges.sort(key=lambda x: x[2])
total = 0
mst = {}
for edge in edges:
	(u, v, w) = edge
	if find(u - 1, nodes) != find(v - 1, nodes):
		union(u - 1, v - 1, nodes)
		if u - 1 in mst:
			mst[u - 1].add((v - 1, w))
		else:
			mst[u - 1] = {(v - 1, w)}
		if v - 1 in mst:
			mst[v - 1].add((u - 1, w))
		else:
			mst[v - 1] = {(u - 1, w)}
(parent, exisits) = bfs(mst, 0)
if exisits:
	maxVal = parent[n - 1][1]
	val = parent[n - 1][0]
	while val != 0:
		maxVal = max(maxVal, parent[val][1])
		val = parent[val][0]
	print(maxVal)
else:
	print('NO PATH EXISTS')


class station(object):

	def __init__(self, id):
		self.id = id
		self.connections = {}

	def __eq__(self, other):
		return self.id == other.id

	def __hash__(self):
		return hash(self.id)

	def __repr__(self):
		return str(self.id)

	def __str__(self):
		return str(self.id)

	def add_connection(self, other, fare):
		self.connections[other] = fare
		other.connections[self] = fare

	def get_fare(self, other):
		return self.connections.get(other, -1)

	def get_connections(self):
		return self.connections.keys()
import heapq
import itertools
pq = []
entry_finder = {}
REMOVED = '<removed-station>'
counter = itertools.count()

def add_station(id, priority=0):
	if id in entry_finder:
		remove_station(id)
	count = next(counter)
	entry = [priority, count, id]
	entry_finder[id] = entry
	heapq.heappush(pq, entry)

def remove_station(id):
	entry = entry_finder.pop(id)
	entry[-1] = REMOVED

def pop_station():
	while pq:
		(priority, count, id) = heapq.heappop(pq)
		if id is not REMOVED:
			del entry_finder[id]
			return id
	raise KeyError('pop from an empty priority queue')

def dijksta(start, destination, stations):
	dist = {start: 0}
	for stat in stations:
		if stat != start:
			dist[stat] = float('inf')
		add_station(stat, dist[stat])
	while len(pq):
		current = pop_station()
		if current == destination:
			return dist[current]
		for neighbor in [x for x in current.get_connections() if x in entry_finder.keys()]:
			alt = max(dist[current], current.get_fare(neighbor))
			if alt < dist[neighbor]:
				dist[neighbor] = alt
				add_station(neighbor, alt)
(num_stations, num_connections) = [int(x) for x in input().split()]
stations = [station(x) for x in range(1, num_stations + 1)]
for _ in range(num_connections):
	(station_a, station_b, fare) = [int(x) for x in input().split()]
	stations[station_a - 1].add_connection(stations[station_b - 1], fare)
cheapest_route = dijksta(stations[0], stations[-1], stations)
if cheapest_route != float('inf'):
	print(cheapest_route)
else:
	print('NO PATH EXISTS')


from heapq import heappush, heappop

def read_graph(n, m):
	g = {}
	for i in range(1, n + 1):
		g[i] = []
	for i in range(m):
		(u, v, c) = [int(x) for x in input().strip().split(' ')]
		g[u].append([c, v])
		g[v].append([c, u])
	return g

def find_distances(g, s, e):
	dist = {}
	for v in g.keys():
		dist[v] = float('inf')
	dist[s] = 0
	q = []
	heappush(q, [0, s])
	while len(q) > 0:
		u = heappop(q)
		if u[0] == s:
			break
		curr_dist = u[0]
		for v in g[u[1]]:
			if curr_dist < v[0]:
				c = v[0]
			else:
				c = curr_dist
			if c < dist[v[1]]:
				heappush(q, [c, v[1]])
				dist[v[1]] = c
	return dist[e]
(n, m) = [int(x) for x in input().strip().split(' ')]
g = read_graph(n, m)
dist = find_distances(g, 1, n)
if float('inf') == dist:
	print('NO PATH EXISTS')
else:
	print(dist)


(n, m) = map(int, input().strip().split(' '))
edges = []
for i in range(m):
	(u, v, cost) = map(int, input().strip().split(' '))
	edges.append((u - 1, v - 1, cost))
edges.sort(key=lambda edge: edge[2])
parents = [i for i in range(n)]
ranks = [0 for i in range(n)]

def find_set(node):
	if parents[node] == node:
		return node
	else:
		return find_set(parents[node])

def union(left_root, right_root):
	left_rank = ranks[left_root]
	right_rank = ranks[right_root]
	if left_rank < right_rank:
		parents[left_root] = right_root
	elif left_rank > right_rank:
		parents[right_root] = left_root
	else:
		parents[right_root] = left_root
		ranks[left_root] += 1
accepted_edges = []
for (u, v, cost) in edges:
	u_root = find_set(u)
	v_root = find_set(v)
	if u_root != v_root:
		accepted_edges.append((u, v, cost))
		union(u_root, v_root)
graph = [[] for i in range(n)]
for (u, v, cost) in accepted_edges:
	graph[u].append((v, cost))
	graph[v].append((u, cost))
queue = [(0, 0)]
unexplored = set(range(1, n))
final_cost = 'NO PATH EXISTS'
while queue:
	(node, cost) = queue.pop()
	if node == n - 1:
		final_cost = cost
		break
	for (neighbor, neighbor_cost) in graph[node]:
		if neighbor in unexplored:
			unexplored.remove(neighbor)
			queue.append((neighbor, max(cost, neighbor_cost)))
print(final_cost)


from heapq import heappush, heappop
(n, e) = [int(v) for v in input().strip().split(' ')]
nodes = {}
debug = False
for i in range(e):
	(a, b, cost) = [int(v) for v in input().strip().split(' ')]
	if a not in nodes:
		nodes[a] = []
	if b not in nodes:
		nodes[b] = []
	nodes[a].append((cost, b))
	nodes[b].append((cost, a))
open_nodes = []
heappush(open_nodes, (0, 1, 0))
seen = {}
cost = 'NO PATH EXISTS'
while len(open_nodes) > 0:
	next_node = heappop(open_nodes)
	if debug:
		print('Next node:', next_node)
	(node_cost, node_num, path_cost) = next_node
	if node_num == n:
		cost = path_cost
		break
	seen[node_num] = 1
	if debug:
		print('Seen:', seen)
	if node_num in nodes:
		for neighbor in nodes[node_num]:
			if neighbor[1] not in seen:
				heappush(open_nodes, (neighbor[0], neighbor[1], max(neighbor[0], path_cost)))
print(cost)


import sys
from collections import deque

def eprint(*argv, **kwargv):
	print(*argv, file=sys.stderr, **kwargv)

class dsetnode:

	def __init__(self, val):
		self.val = val
		self.parent = self

class dset:

	def __init__(self):
		self.nodes = {}
		self.parents = {}

	def add(self, val):
		if val not in self.nodes:
			self.nodes[val] = set()
			self.nodes[val].add(val)
			self.parents[val] = val

	def find(self, val):
		return self.parents[val]

	def unite(self, val1, val2):
		root1 = self.find(val1)
		root2 = self.find(val2)
		if root1 != root2:
			(rootbig, rootsmall) = (root1, root2) if len(self.nodes[root2]) < len(self.nodes[root1]) else (root2, root1)
			for child in self.nodes[rootsmall]:
				self.parents[child] = rootbig
				self.nodes[rootbig].add(child)
			return rootbig
		else:
			return root1
(N, E) = list(map(int, input().split(' ')))
edges = []
for i in range(E):
	(a, b, c) = list(map(int, input().strip().split()))
	edges.append((a, b, c))
edges = sorted(edges, key=lambda x: x[2])
maxval = -1
found = False
d = dset()
for i in range(1, N + 1):
	d.add(i)
for (a, b, c) in edges:
	if d.find(a) == d.find(b):
		continue
	if maxval < c:
		maxval = c
	root = d.unite(a, b)
	if root == d.find(1) and root == d.find(N):
		found = True
		break
if found:
	print(maxval)
else:
	print('NO PATH EXISTS')


(n, e) = map(int, input().strip().split())
parent = [-1] * n

def find(n):
	if parent[n] < 0:
		return n
	pt = find(parent[n])
	parent[n] = pt
	return pt
edges = []
for ee in range(e):
	(a, b, c) = map(int, input().strip().split())
	a -= 1
	b -= 1
	edges.append((c, a, b))
edges.sort()
if find(0) == find(n - 1):
	print(0)
else:
	for (c, a, b) in edges:
		a = find(a)
		b = find(b)
		if a != b:
			if parent[a] == parent[b]:
				parent[b] -= 1
			if parent[a] > parent[b]:
				parent[a] = b
			else:
				parent[b] = a
		if find(0) == find(n - 1):
			print(c)
			break
	else:
		print('NO PATH EXISTS')


from collections import defaultdict

class MinHeapMap:

	def __init__(self, arr=[]):
		self.heap = arr
		self.elems = len(arr)
		self._map = {v[0]: i for (i, v) in enumerate(arr)}

	def parent(self, i):
		return (i - 1) // 2

	def swap(self, i, j):
		(self.heap[i], self.heap[j]) = (self.heap[j], self.heap[i])
		(self._map[self.heap[j][0]], self._map[self.heap[i][0]]) = (j, i)

	def update_key(self, key, val):
		i = self._map[key]
		self.heap[i][1] = val
		return i

	def contains_key(self, key):
		return key in self._map

	def value_by_key(self, key):
		return self.heap[self._map[key]][1]

	def decrease_key(self, key, val):
		if key not in self._map:
			return False
		pos = self.update_key(key, val)
		p = self.parent(pos)
		while pos != 0 and self.heap[pos][1] < self.heap[p][1]:
			self.swap(pos, p)
			(pos, p) = (p, self.parent(p))

	def increase_key(self, key, val):
		if key not in M:
			return False
		pos = self.update_key(key, val)
		self.heapify(pos)

	def heapify(self, i):
		(l, r, s) = (2 * i + 1, 2 * i + 2, i)
		if l < self.elems and self.heap[l][1] < self.heap[s][1]:
			s = l
		if r < self.elems and self.heap[r][1] < self.heap[s][1]:
			s = r
		if s != i:
			self.swap(s, i)
			self.heapify(s)

	def extract_min(self):
		temp = self.heap[0]
		self.swap(0, self.elems - 1)
		del self._map[self.heap[-1][0]]
		self.heap.pop()
		self.elems = len(self.heap)
		self.heapify(0)
		return temp

	def print_heap(self):
		print(self.heap)

def heap_extract(heap, cost_pop, cost_othr):
	(v, c) = heap.extract_min()
	cost_pop[v] = c
	if v in cost_othr:
		return max(c, cost_othr[v])
	for vt in G[v]:
		if heap.contains_key(vt):
			max_cost = max(c, W[v][vt])
			if max_cost < heap.value_by_key(vt):
				heap.decrease_key(vt, max_cost)

def Rupture(G, W, N):
	(arr_f, arr_b) = ([[i, float('inf')] for i in range(1, N + 1)], [[i, float('inf')] for i in range(N, 0, -1)])
	arr_f[0][1] = arr_b[0][1] = 0
	(Cost_f, Cost_b) = ({}, {})
	Cost_f[1] = Cost_b[N] = 0
	(fHeap, bHeap) = (MinHeapMap(arr_f), MinHeapMap(arr_b))
	while fHeap and bHeap:
		forward = heap_extract(fHeap, Cost_f, Cost_b)
		if forward:
			return 'NO PATH EXISTS' if forward == float('inf') else forward
		backward = heap_extract(bHeap, Cost_b, Cost_f)
		if backward:
			return 'NO PATH EXISTS' if backward == float('inf') else backward
(N, E) = [int(i) for i in input().split()]
(G, W) = (defaultdict(list), defaultdict(dict))
for _ in range(E):
	e = [int(i) for i in input().split()]
	G[e[0]].append(e[1])
	G[e[1]].append(e[0])
	W[e[0]][e[1]] = e[2]
	W[e[1]][e[0]] = e[2]
print(Rupture(G, W, N))


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


import sys
(N, M) = (int(a) for a in sys.stdin.readline().split())
W = {}
E = [set() for n in range(N)]
for e0 in range(M):
	(a, b, w) = (int(a) for a in sys.stdin.readline().split())
	W[a - 1, b - 1] = w
	W[b - 1, a - 1] = w
	E[b - 1].add(a - 1)
	E[a - 1].add(b - 1)
import math
D = [math.inf] * N
D[0] = 0
Q = {0}
while Q:
	N = set()
	if D[-1] == 97306:
		break
	for q in Q:
		if D[q] > D[-1]:
			continue
		for w in E[q]:
			d = max(W[q, w] - D[q], 0) + D[q]
			if D[w] > d:
				D[w] = d
				N.add(w)
	Q = N
if D[-1] < math.inf:
	print(D[-1])
else:
	print('NO PATH EXISTS')


from heapq import heappop, heappush
(N, E) = [int(x) for x in input().split()]
G = [[] for _ in range(N)]
for _ in range(E):
	(s, d, c) = [int(x) for x in input().split()]
	(s, d) = (s - 1, d - 1)
	G[s].append((d, c))
	G[d].append((s, c))
h = [(0, 0)]
v = set()
r = -1
while h:
	(c, s) = heappop(h)
	if s == N - 1:
		r = c
		break
	v.add(s)
	for (d, f) in G[s]:
		if d in v:
			continue
		heappush(h, (max(c, f), d))
if r == -1:
	print('NO PATH EXISTS')
else:
	print(r)


import math
from heapq import *

class Node:

	def __init__(self):
		self.children = set()
(n, m) = map(int, input().strip().split())
dists = [math.inf for _ in range(n + 1)]
heap = [(0, 1)]
nodes = [Node() for _ in range(n + 1)]
for m_i in range(m):
	(u, v, c) = map(int, input().strip().split())
	nodes[u].children.add((c, v))
	nodes[v].children.add((c, u))
while heap:
	node = heappop(heap)
	dists[node[1]] = node[0]
	if node[1] == n:
		break
	for c_i in nodes[node[1]].children:
		(c, v) = c_i
		if dists[v] != math.inf:
			continue
		real_cost = c - node[0]
		if real_cost < 0:
			real_cost = 0
		total_cost = real_cost + node[0]
		heappush(heap, (total_cost, v))
if dists[n] == math.inf:
	print('NO PATH EXISTS')
else:
	print(dists[n])


from random import *
import operator
parent = [-100]
rank = [-100]

def makeset(i, parent, rank):
	parent.append(i)
	rank.append(0)

def find(i, parent):
	if i != parent[i]:
		parent[i] = find(parent[i], parent)
	return parent[i]

def union(u, v, rank, parent):
	u_id = find(u, parent)
	v_id = find(v, parent)
	if u_id == v_id:
		return maximum
	elif rank[u_id] > rank[v_id]:
		parent[v_id] = u_id
	else:
		parent[u_id] = v_id
		if rank[u_id] == rank[v_id]:
			rank[v_id] = rank[v_id] + 1

def mst(node_list, distances):
	for i in node_list:
		makeset(i, parent, rank)
	sorted_edge = sorted(distances.items(), key=operator.itemgetter(1))
	for (nodes, distance) in sorted_edge:
		(u, v) = nodes
		if find(u, parent) != find(v, parent):
			union(u, v, rank, parent)
			if find(1, parent) == find(node_list[-1], parent):
				return distance
	return 'NO PATH EXISTS'

def sol(adj, N):
	print(mst([i for i in range(1, N + 1)], adj))

def main():
	(N, E) = list(map(int, input().split()))
	adj = {}
	for _ in range(E):
		(u, v, distance) = list(map(int, input().split()))
		adj[u, v] = distance
		adj[v, u] = distance
	sol(adj, N)

def test():
	N = randint(1, 50001)
	adj = {}
	for _ in range(1, 500001):
		(u, v) = (randint(1, N), randint(1, N))
		distance = randint(1, 10 ** 7)
		if u not in adj:
			adj[u] = {}
		adj[u][v] = distance
		if v not in adj:
			adj[v] = {}
		adj[v][u] = distance
		sol(adj, N)
main()


from heapq import *
(N, E) = map(int, input().split())
e = [[] for _ in range(N)]
for i in range(E):
	(v1, v2, f) = map(int, input().split())
	v1 -= 1
	v2 -= 1
	e[v1].append((v2, f))
	e[v2].append((v1, f))
v = [False] * N
h = [(0, 0)]
ans = -1
while len(h) != 0:
	(c, p) = heappop(h)
	v[p] = True
	if p == N - 1:
		ans = c
		break
	for (pn, ec) in e[p]:
		if v[pn]:
			continue
		heappush(h, (max(c, ec), pn))
if ans == -1:
	print('NO PATH EXISTS')
else:
	print(ans)


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)
(N, E) = read_ints()
graph = build_graph(E)
result = calculate(graph, N)
if result is None:
	print('NO PATH EXISTS')
else:
	print(result)


from heapq import heappush, heappop

def lstin():
	return list(map(int, input().strip().split()))

def dijkstra(edges, N):
	costs = [None] + [float('inf')] * N
	pq = [(0, 1)]
	while pq:
		(uc, u) = heappop(pq)
		if uc < costs[u]:
			costs[u] = uc
			for (v, vc) in edges[u]:
				cc = max(uc, vc)
				if cc < costs[v]:
					heappush(pq, (cc, v))
	return costs[N]
(N, E) = lstin()
edges = [None] + [list() for _ in range(N)]
for _ in range(E):
	(u, v, c) = lstin()
	edges[u].append((v, c))
	edges[v].append((u, c))
cumcost = dijkstra(edges, N)
print(cumcost if cumcost < float('inf') else 'NO PATH EXISTS')


maxw = 10 ** 7

def shortest_path(E, n, m):
	E.sort(key=lambda x: x[2])
	G = [[] for i in range(n)]
	W = {}
	S = [i for i in range(n)]
	U = {i: [i] for i in range(n)}
	for (u, v, w) in E:
		if not S[u] == S[v]:
			G[u].append(v)
			G[v].append(u)
			W[u, v] = w
			W[v, u] = w
			if len(U[S[u]]) < len(U[S[v]]):
				(u, v) = (v, u)
			Sv = U.pop(S[v])
			U[S[u]] += Sv
			for node in Sv:
				S[node] = S[u]
		if S[0] == S[n - 1]:
			break
	if not S[0] == S[n - 1]:
		return 'NO PATH EXISTS'
	P = [-1] * n
	queue = [0]
	while len(queue) > 0:
		newqueue = []
		for node in queue:
			for child in G[node]:
				if P[child] == -1:
					P[child] = node
					newqueue.append(child)
		queue = newqueue
	wmax = 0
	node = n - 1
	while node > 0:
		wmax = max(wmax, W[node, P[node]])
		node = P[node]
	return wmax
(n, m) = list(map(int, input().strip().split()))
E = []
for i in range(m):
	(u, v, w) = list(map(int, input().strip().split()))
	E.append((u - 1, v - 1, w))
print(shortest_path(E, n, m))


from collections import defaultdict
from heapq import *

def dijkstra(edges, f, t):
	g = defaultdict(list)
	for (l, r, c) in edges:
		g[l].append((c, r))
		g[r].append((c, l))
	(q, seen) = ([(0, f, ())], set())
	while q:
		(cost, v1, path) = heappop(q)
		if v1 not in seen:
			seen.add(v1)
			path = (v1, path)
			if v1 == t:
				return cost
			for (c, v2) in g.get(v1, ()):
				if v2 not in seen:
					heappush(q, (max(cost, c), v2, path))
	return 'NO PATH EXISTS'
edges = list()
line0 = input().split()
N = line0[0]
E = int(line0[1])
for idx in range(E):
	edge = input().split()
	edges.append((edge[0], edge[1], int(edge[2])))
print(dijkstra(edges, '1', N))


class UnionFind:

	def __init__(self, n):
		self._nodes = list(range(n))

	def _root(self, u):
		root = u
		while root != self._nodes[root]:
			root = self._nodes[root]
		while u != root:
			(self._nodes[u], u) = (root, self._nodes[u])
		return root

	def are_connected(self, u, v):
		return self._root(u) == self._root(v)

	def connect(self, u, v):
		ru = self._root(u)
		rv = self._root(v)
		if ru != rv:
			self._nodes[ru] = rv
(nV, nE) = map(int, input().split())
E = []
for _ in range(nE):
	(b, e, w) = map(int, input().split())
	E.append((w, b - 1, e - 1))
E.sort()
uf = UnionFind(nV)
for (w, b, e) in E:
	uf.connect(b, e)
	if uf.are_connected(0, nV - 1):
		print(w)
		break
else:
	print('NO PATH EXISTS')


import sys
MOD = 10 ** 9 + 7

def parseInt():
	return list(map(int, input().split()))
sys.setrecursionlimit(100000)
(n, m) = parseInt()
edges = [[] for i in range(n)]
for _ in range(m):
	(u, v, c) = parseInt()
	(u, v) = (u - 1, v - 1)
	edges[u].append((v, c))
	edges[v].append((u, c))
costs = [float('inf') for i in range(n)]
costs[0] = 0
currentLevel = set()
currentLevel.add(0)
while currentLevel:
	nextLevel = set()
	for node in currentLevel:
		for (neighbor, cost) in edges[node]:
			currentCost = max(cost, costs[node])
			if currentCost < costs[neighbor]:
				costs[neighbor] = currentCost
				nextLevel.add(neighbor)
	currentLevel = set(list(nextLevel))
print(costs[-1] if costs[-1] != float('inf') else 'NO PATH EXISTS')


import heapq
import sys

def readEdge():
	line = input().split(' ')
	return tuple(map(int, line))
line = input().split(' ')
n = int(line[0])
e = int(line[1])
x = sys.maxsize
nodes = [0]
edgesOut = [[]]
for i in range(1, n + 1):
	nodes.append(x)
	edgesOut.append([])
for i in range(0, e):
	(j1, j2, c) = readEdge()
	edgesOut[j1].append((c, j2))
	edgesOut[j2].append((c, j1))
pq = list(edgesOut[1])
heapq.heapify(pq)
stillLooking = True
result = -1
while stillLooking:
	if len(pq) == 0:
		break
	(c, endPoint) = heapq.heappop(pq)
	if endPoint == n:
		result = c
		break
	if c < nodes[endPoint]:
		nodes[endPoint] = c
		for (c2, nextPoint) in edgesOut[endPoint]:
			heapq.heappush(pq, (max(c2, c), nextPoint))
if result > 0:
	print(result)
else:
	print('NO PATH EXISTS')


import sys

def solve(g, fr, to):
	path_cache = {i: None for i in g}
	path_cache[fr] = 0
	prev_cache = {i: None for i in g}
	stack = {fr}
	while stack:
		node = stack.pop()
		for (ch, c) in g[node]:
			new_c = path_cache[node]
			if c > path_cache[node]:
				new_c = c
			if path_cache[ch] is None or path_cache[ch] > new_c:
				path_cache[ch] = new_c
				prev_cache[ch] = node
				stack.add(ch)
	return path_cache[to]
(n, m) = map(int, input().split())
g = {i: list() for i in range(1, n + 1)}
for _ in range(m):
	(fr, to, c) = map(int, input().split())
	g[fr].append((to, c))
	g[to].append((fr, c))
u = solve(g, min(g), max(g))
if u is None:
	u = 'NO PATH EXISTS'
print(u)


import heapq

def findpath(array, i):
	q = []
	for j in array[i]:
		q.append([j[1], j[0], i])
	dist = [0 for x in range(len(array))]
	heapq.heapify(q)
	while len(q) > 0:
		node = heapq.heappop(q)
		if dist[node[1]] == 0:
			if node[0] > dist[node[2]]:
				dist[node[1]] = node[0]
			else:
				dist[node[1]] = dist[node[2]]
		for j in array[node[1]]:
			if dist[j[0]] == 0 and j[0] != 0:
				heapq.heappush(q, [j[1], j[0], node[1]])
	return dist[-1]
(n, e) = input().split()
n = int(n)
e = int(e)
array = [[] for x in range(n)]
for x0 in range(e):
	(int_1, int_2, int_3) = input().split()
	int_1 = int(int_1)
	int_2 = int(int_2)
	int_3 = int(int_3)
	array[int_1 - 1].append([int_2 - 1, int_3])
	array[int_2 - 1].append([int_1 - 1, int_3])
ans = findpath(array, 0)
if ans == 0:
	print('NO PATH EXISTS')
else:
	print(ans)


from heapq import *

def dijkstra(nodes, graph, source, target):
	q = []
	heappush(q, (0, source))
	d = [-1 for i in range(nodes)]
	d[source] = 0
	while q:
		(distance, u) = heappop(q)
		if u == target:
			return distance
		if d[u] <= 0:
			d[u] = distance
			for v in graph[u]:
				if d[v] > -1:
					continue
				cost = distance + max(0, graph[u][v] - distance)
				heappush(q, (cost, v))
	return None

def solve():
	(n, m) = map(int, input().split())
	g = [{} for i in range(n)]
	for a1 in range(m):
		(x, y, r) = map(int, input().split())
		(x, y) = (x - 1, y - 1)
		g[x][y] = g[y][x] = r
	d = dijkstra(n, g, 0, n - 1)
	if d == None:
		print('NO PATH EXISTS')
	else:
		print(d)
solve()


import collections
import heapq
(n, e) = [int(x) for x in input().strip().split()]
graph = collections.defaultdict(list)
for _ in range(e):
	(node1, node2, weight) = [int(x) for x in input().strip().split()]
	graph[node1].append((node2, weight))
	graph[node2].append((node1, weight))
frontier = [(0, 1)]
visited = set([1])
pathWeight = -1
while len(frontier) != 0:
	(weight, node) = heapq.heappop(frontier)
	if node == n:
		pathWeight = weight
		break
	for (nextNode, nextWeight) in graph[node]:
		if nextNode not in visited:
			heapq.heappush(frontier, (max(weight, nextWeight), nextNode))
	visited.add(node)
if pathWeight == -1:
	print('NO PATH EXISTS')
else:
	print(pathWeight)


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


(n, e) = map(int, input().strip().split())
parent = [-1] * n

def find(n):
	if parent[n] < 0:
		return n
	pt = find(parent[n])
	parent[n] = pt
	return pt
edges = []
for ee in range(e):
	(a, b, c) = map(int, input().strip().split())
	a -= 1
	b -= 1
	edges.append((c, a, b))
edges.sort()
if find(0) == find(n - 1):
	print(0)
else:
	for (c, a, b) in edges:
		a = find(a)
		b = find(b)
		if a != b:
			if parent[a] == parent[b]:
				parent[b] -= 1
			if parent[a] > parent[b]:
				parent[a] = b
			else:
				parent[b] = a
		if find(0) == find(n - 1):
			print(c)
			break
	else:
		print('NO PATH EXISTS')


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


import queue

class Dijkstra:

	def __init__(self, tamanio, inicio):
		self.cola = queue.PriorityQueue()
		self.nodo_partida = inicio
		self.Grafo = [[] for i in range(tamanio)]
		self.nodos = [[True, 1000000000] for i in range(tamanio)]

	def Crear_grafo(self, num_aristas):
		for e in range(num_aristas):
			(i, j, w) = [int(i) for i in input().split()]
			self.Grafo[i - 1] += [(j - 1, w)]
			self.Grafo[j - 1] += [(i - 1, w)]

	def camino_corto(self):
		self.cola.put((0, self.nodo_partida))
		self.nodos[self.nodo_partida][1] = 0
		while not self.cola.empty():
			elemento = self.cola.get()
			if self.nodos[elemento[1]][0]:
				self.nodos[elemento[1]][0] = False
				for i in self.Grafo[elemento[1]]:
					if self.nodos[i[0]][0]:
						tarifa = i[1] - self.nodos[elemento[1]][1]
						if tarifa < 0:
							tarifa = 0
						if self.nodos[i[0]][1] > self.nodos[elemento[1]][1] + tarifa:
							self.nodos[i[0]][1] = self.nodos[elemento[1]][1] + tarifa
							self.cola.put((self.nodos[i[0]][1], i[0]))

	def imprimir(self, x):
		if not self.nodos[x][0]:
			print(self.nodos[x][1])
		else:
			print('NO PATH EXISTS')
(n, num_ar) = [int(i) for i in input().split()]
D = Dijkstra(n, 0)
D.Crear_grafo(num_ar)
D.camino_corto()
D.imprimir(n - 1)


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_stations(current, graph, stations_queue, costs_cache):
	for (station, cost) in graph[current]:
		base_cost = costs_cache[current]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and costs_cache[station] < cost:
			continue
		stations_queue.put((cost, station))

def calculate(graph, N):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_stations(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_stations(current, graph, stations_queue, costs_cache)

def main():
	(N, E) = read_ints()
	graph = build_graph(E)
	result = calculate(graph, N)
	if result is None:
		print('NO PATH EXISTS')
	else:
		print(result)
main()


import sys
from collections import defaultdict
import queue
import itertools
import heapq

class PriorityQueue:

	def __init__(self):
		self.h = []
		self.size = 0
		self.entry_finder = {}
		self.counter = itertools.count()

	def add(self, task, priority):
		if task in self.entry_finder:
			self.remove_task(task)
		count = next(self.counter)
		entry = [priority, count, task]
		self.entry_finder[task] = entry
		heapq.heappush(self.h, entry)
		self.size += 1

	def remove_task(self, task):
		entry = self.entry_finder.pop(task)
		entry[-1] = 'removed'
		self.size -= 1

	def is_empty(self):
		return self.size == 0

	def pop_task(self):
		while self.h:
			(priority, count, task) = heapq.heappop(self.h)
			if task is not 'removed':
				del self.entry_finder[task]
				self.size -= 1
				return task
		raise KeyError('pop from empty pq')

class Graph:

	def __init__(self, N):
		self.nodes = defaultdict(set)
		self.edges = {}
		self.size = N

	def add(self, node1, node2, cost):
		self.edges[node1, node2] = cost
		self.edges[node2, node1] = cost
		self.nodes[node1].add(node2)
		self.nodes[node2].add(node1)

	def modified_dikstra(self):
		n = self.size
		dists = [1000000] * (n + 1)
		parents = [-1] * (n + 1)
		dists[1] = 0
		pq = PriorityQueue()
		for i in range(1, n + 1):
			pq.add(i, dists[i])
		while not pq.is_empty():
			u = pq.pop_task()
			adj = self.nodes[u]
			for v in adj:
				new_distance = max(0, self.edges[u, v] - dists[u])
				if new_distance + dists[u] < dists[v]:
					dists[v] = dists[u] + new_distance
					pq.add(v, new_distance)
		return dists[n]

def make_graph(input_string):
	input_string = input_string.split('\n')
	g = Graph()
	(N, E) = input_string.pop(0).strip().split()
	(N, E) = [int(N), int(E)]
	for line in input_string:
		(n1, n2, c) = line.strip().split()
		(n1, n2, c) = [int(n1), int(n2), int(c)]
		g.add(n1, n2, c)
	return g

def jackGoesToRapture(N, edges):
	pass
(N, E) = input().strip().split(' ')
(N, E) = [int(N), int(E)]
edges = []
g = Graph(N)
for edges_i in range(E):
	edges_t = [int(edges_temp) for edges_temp in input().strip().split(' ')]
	edges.append(edges_t)
	g.add(edges_t[0], edges_t[1], edges_t[2])
result = g.modified_dikstra()
if result == 1000000:
	print('NO PATH EXISTS')
else:
	print(result)


import sys
import queue

def read_ints():
	return [int(x) for x in sys.stdin.readline().split()]

def build_graph(E):
	graph = {}
	while E > 0:
		(s1, s2, cost) = read_ints()
		if s1 not in graph:
			graph[s1] = []
		graph[s1].append((s2, cost))
		if s2 not in graph:
			graph[s2] = []
		graph[s2].append((s1, cost))
		E -= 1
	return graph

def next_station(ind, graph, stations_queue, costs_cache):
	for (station, cost) in graph[ind]:
		base_cost = costs_cache[ind]
		cost = base_cost + max(0, cost - base_cost)
		if station in costs_cache and cost < costs_cache[station]:
			continue
		stations_queue.put((cost, station))

def jackGoesToRapture(graph):
	costs_cache = {1: 0}
	stations_queue = queue.PriorityQueue()
	next_station(1, graph, stations_queue, costs_cache)
	while not stations_queue.empty():
		(cost, current) = stations_queue.get()
		if current == N:
			return cost
		if current in costs_cache:
			continue
		costs_cache[current] = cost
		next_station(current, graph, stations_queue, costs_cache)
	return 'NO PATH EXISTS'
(N, E) = (N, E) = read_ints()
graph = build_graph(E)
result = jackGoesToRapture(graph)
print(result)


from math import inf
from heapq import heappush, heappop

def solve(N, adj):
	costs = {x: inf for x in range(1, N + 1)}
	costs[1] = 0
	pq = [(0, 1)]
	while len(pq):
		(curr_cost, curr) = heappop(pq)
		if curr == N:
			return curr_cost
		for nei in adj[curr]:
			dijkstra_cost = max(curr_cost, adj[curr][nei])
			if dijkstra_cost < costs[nei]:
				costs[nei] = dijkstra_cost
				heappush(pq, (dijkstra_cost, nei))
	return 'NO PATH EXISTS'
(N, E) = map(int, input().split())
adj = {x: dict() for x in range(1, N + 1)}
for _ in range(E):
	(a, b, c) = map(int, input().split())
	adj[a][b] = c
	adj[b][a] = c
result = solve(N, adj)
print(result)


import sys
import heapq
(N, E) = input().strip().split(' ')
(N, E) = [int(N), int(E)]
edges = [[] for i in range(N)]
for edges_i in range(E):
	(A, B, C) = map(int, input().split())
	A -= 1
	B -= 1
	edges[A].append((B, C))
	edges[B].append((A, C))
cost = [10 ** 10 for i in range(N)]
cost[0] = 0
q = [(0, 0)]
while len(q) > 0:
	(curr_cost, node) = heapq.heappop(q)
	if curr_cost > cost[node]:
		continue
	for (neigh, c) in edges[node]:
		next_cost = max(c, curr_cost)
		if next_cost < cost[neigh]:
			cost[neigh] = next_cost
			heapq.heappush(q, (next_cost, neigh))
	if node == N - 1:
		break
if cost[N - 1] == 10 ** 10:
	print('NO PATH EXISTS')
else:
	print(cost[N - 1])


import os
import sys
import heapq

def findMinFare(edges, s, t):
	INF = 10 ** 7 + 1
	n = len(edges)
	dists = [INF for _ in range(n)]
	dists[s] = 0
	visited = [False for _ in range(n)]
	h = []
	heapq.heappush(h, (0, s))
	while len(h) > 0:
		(current_dist, next_u) = heapq.heappop(h)
		if visited[next_u]:
			continue
		for edge in edges[next_u]:
			(v, weight) = edge
			dist_s_u_v = max(weight, current_dist)
			if not visited[v] and dists[v] > dist_s_u_v:
				dists[v] = dist_s_u_v
				heapq.heappush(h, (dist_s_u_v, v))
		visited[next_u] = True
	if dists[t] == INF:
		return 'NO PATH EXISTS'
	return str(dists[t])
(n, m) = map(int, input().split())
edges = [[] for _ in range(n)]
for edge in range(m):
	(u, v, weight) = map(int, input().split())
	u -= 1
	v -= 1
	edges[u].append((v, weight))
	edges[v].append((u, weight))
result = findMinFare(edges, 0, n - 1)
print(result)


from collections import defaultdict
import heapq as H
import os
import sys

class graph:

	def __init__(self):
		self.g = defaultdict(list)

	def add(self, a, b, c):
		self.g[a] += [(a, b, c)]
		self.g[b] += [(b, a, c)]

	def min_cost(self, s, e):
		h = [(0, s)]
		closed = set()
		while h:
			(cost, n) = H.heappop(h)
			if n == e:
				return cost
			if n not in closed:
				closed.add(n)
				for (_, nb, c) in self.g[n]:
					H.heappush(h, (max(c, cost), nb))
		return 'NO PATH EXISTS'
(g_nodes, g_edges) = map(int, input().split())
g_from = [0] * g_edges
g_to = [0] * g_edges
g_weight = [0] * g_edges
g = graph()
for g_itr in range(g_edges):
	(a, b, c) = map(int, input().split())
	g.add(a, b, c)
print(g.min_cost(1, g_nodes))


import os
import sys
import heapq
from collections import defaultdict

class PQ:

	def __init__(self):
		self.data = []

	def enque(self, k, v):
		heapq.heappush(self.data, (k, v))

	def deque(self):
		return heapq.heappop(self.data)

	def __len__(self):
		return len(self.data)

def dijkstra(adj, weights, s, t, N):
	dist_to = [sys.maxsize] * N
	pq = PQ()
	pq.enque(s, 0)
	dist_to[s] = 0
	while len(pq):
		(_, v) = pq.deque()
		for vn in adj[v]:
			W = max(0, weights[v, vn] - dist_to[v])
			new_dist = dist_to[v] + W
			if dist_to[vn] > new_dist:
				pq.enque(new_dist, vn)
				dist_to[vn] = new_dist
	return dist_to[t]
(g_nodes, g_edges) = map(int, input().split())
g_from = [0] * g_edges
g_to = [0] * g_edges
g_weight = [0] * g_edges
adj = defaultdict(set)
weights = {}
for g_itr in range(g_edges):
	(v_from, v_to, weight) = map(int, input().split())
	v_from -= 1
	v_to -= 1
	adj[v_from].add(v_to)
	adj[v_to].add(v_from)
	weights[v_from, v_to] = weight
	weights[v_to, v_from] = weight
res = dijkstra(adj, weights, 0, g_nodes - 1, g_nodes)
if res == sys.maxsize:
	print('NO PATH EXISTS')
else:
	print(res)


import os
import sys

def cost(a):
	return a[2]

def collapse(eList, nodes):
	componentList = [[i] for i in range(nodes)]
	componentMap = [i for i in range(nodes)]
	for e in eList:
		if componentMap[e[0]] < componentMap[e[1]]:
			componentList[componentMap[e[0]]].extend(componentList[componentMap[e[1]]])
			for i in componentList[componentMap[e[1]]]:
				componentMap[i] = componentMap[e[0]]
		elif componentMap[e[1]] < componentMap[e[0]]:
			componentList[componentMap[e[1]]].extend(componentList[componentMap[e[0]]])
			for i in componentList[componentMap[e[0]]]:
				componentMap[i] = componentMap[e[1]]
		if componentMap[0] == componentMap[-1]:
			return e[2]
	return 'NO PATH EXISTS'
(g_nodes, g_edges) = map(int, input().split())
g_from = [0] * g_edges
g_to = [0] * g_edges
g_weight = [0] * g_edges
edgelist = []
for g_itr in range(g_edges):
	(g_from[g_itr], g_to[g_itr], g_weight[g_itr]) = map(int, input().split())
	edgelist.append((g_from[g_itr] - 1, g_to[g_itr] - 1, g_weight[g_itr]))
edgelist = sorted(edgelist, key=cost)
print(collapse(edgelist, g_nodes))


import sys
from heapq import heappush, heappop

def djkistra(g_nodes, edges):
	heap = []
	heappush(heap, (0, 1))
	distance = [10000000000 for i in range(g_nodes + 1)]
	while len(heap) > 0:
		(sum, elem) = heappop(heap)
		if elem == g_nodes:
			return sum
		for (neigh, neigh_weight) in edges[elem]:
			t = 0 if neigh_weight - sum < 1 else neigh_weight - sum
			if t + sum < distance[neigh]:
				distance[neigh] = t + sum
				heappush(heap, (distance[neigh], neigh))
	return 'NO PATH EXISTS'
(g_nodes, g_edges) = map(int, input().split())
edges = [[] for i in range(g_nodes + 1)]
for g_itr in range(g_edges):
	(g_from, g_to, g_weight) = map(int, input().split())
	edges[g_from].append((g_to, g_weight))
	edges[g_to].append((g_from, g_weight))
print(djkistra(g_nodes, edges))


import sys
from collections import defaultdict

class indexed_min_pq:

	def __init__(self, N):
		self.maxN = N
		self.n = 0
		self.keys = [sys.maxsize for _ in range(N)]
		self.pq = [-1] * (N + 1)
		self.qp = [-1] * (N + 1)

	def contains(self, i):
		assert self.maxN > i >= 0
		return self.qp[i] != -1

	def is_empty(self):
		return self.n == 0

	def insert(self, index, key):
		assert not self.contains(index)
		assert self.maxN > index >= 0
		self.n += 1
		self.qp[index] = self.n
		self.pq[self.n] = index
		self.keys[index] = key
		self._swim(self.n)

	def pop_min(self):
		mindex = self.pq[1]
		self._exch(1, self.n)
		self.n -= 1
		self._sink(1)
		self.qp[mindex] = -1
		self.keys[mindex] = sys.maxsize
		self.pq[self.n + 1] = -1
		return mindex

	def decrease_key(self, index, key):
		assert self.maxN > index >= 0
		self.keys[index] = key
		self._swim(self.qp[index])

	def _exch(self, i, j):
		(self.pq[i], self.pq[j]) = (self.pq[j], self.pq[i])
		self.qp[self.pq[i]] = i
		self.qp[self.pq[j]] = j

	def _swim(self, i):
		while i > 1 and self.keys[self.pq[i // 2]] > self.keys[self.pq[i]]:
			self._exch(i, i // 2)
			i //= 2

	def _sink(self, i):
		while 2 * i <= self.n:
			j = 2 * i
			if j < self.n and self.keys[self.pq[j]] > self.keys[self.pq[j + 1]]:
				j += 1
			if self.keys[self.pq[i]] <= self.keys[self.pq[j]]:
				break
			self._exch(i, j)
			i = j

def dijkstra(G, V, s):
	dist_to = [sys.maxsize] * V
	pq = indexed_min_pq(V)
	pq.insert(s, 0)
	dist_to[s] = 0
	while not pq.is_empty():
		u = pq.pop_min()
		for (v, w) in G[u]:
			candidate = dist_to[u] + max(0, w - dist_to[u])
			if candidate < dist_to[v]:
				dist_to[v] = candidate
				if pq.contains(v):
					pq.decrease_key(v, dist_to[v])
				else:
					pq.insert(v, dist_to[v])
	return dist_to

def read_graph():
	graph = defaultdict(set)
	(V, E) = map(int, input().split(' '))
	for _ in range(E):
		(u, v, w) = map(int, input().split(' '))
		(u, v) = (u - 1, v - 1)
		graph[u].add((v, w))
		graph[v].add((u, w))
	return (graph, V)
(G, V) = read_graph()
ret = dijkstra(G, V, 0)
if ret[V - 1] == sys.maxsize:
	print('NO PATH EXISTS')
else:
	print(ret[V - 1])


class Node:

	def __init__(self, id, key):
		(self.id, self.key) = (id, key)

	def __str__(self):
		return '(id=%d,key=%d)' % (self.id, self.key)

class MinHeap:

	def __init__(self, cap):
		(self.buf, self.size, self.npos) = ([None] * (cap + 1), 0, [-1] * (cap + 1))

	def __bool__(self):
		return self.size

	def top(self):
		return self.buf[0]

	def getById(self, p):
		return self.buf[self.npos[p]] if self.npos[p] != -1 else None

	def replace(self, node):
		if self.npos[node.id] == -1:
			self.push(node)
		else:
			okey = self.buf[self.npos[node.id]].key
			if okey == node.key:
				return
			self.buf[self.npos[node.id]] = node
			if okey > node.key:
				self.siftUp(self.npos[node.id])
			else:
				self.siftDown(self.npos[node.id])

	def push(self, node):
		(self.buf[self.size], self.npos[node.id]) = (node, self.size)
		self.size += 1
		self.siftUp(self.size - 1)

	def pop(self):
		r = self.buf[0]
		self.npos[r.id] = -1
		self.buf[0] = self.buf[self.size - 1]
		self.siftDown(0)
		self.size -= 1
		return r

	def remove(self, i):
		if self.npos[i] >= 0:
			self.buf[self.npos[i]] = self.buf[self.size - 1]
			self.siftDown(self.npos[i])
			self.size -= 1
			self.npos[i] = -1

	def siftUp(self, p):
		ct = self.buf[p]
		while p != 0:
			iParent = (p - 1) // 2
			pn = self.buf[iParent]
			if pn.key > ct.key:
				self.buf[p] = pn
				self.npos[pn.id] = p
				p = iParent
			else:
				break
		if self.npos[ct.id] != p:
			self.buf[p] = ct
			self.npos[ct.id] = p
			self.siftDown(p)

	def siftDown(self, p):
		ct = self.buf[p]
		while True:
			(nxleft, nx, nv) = (p + p + 1, -1, ct.key)
			if nxleft >= self.size:
				break
			if self.buf[nxleft].key < ct.key:
				(nx, nv) = (nxleft, self.buf[nxleft].key)
			if nxleft + 1 < self.size:
				if self.buf[nxleft + 1].key < nv:
					nx = nxleft + 1
			if nx == -1:
				break
			pn = self.buf[nx]
			self.buf[p] = pn
			self.npos[pn.id] = p
			p = nx
		if self.npos[ct.id] != p:
			self.buf[p] = ct
			self.npos[ct.id] = p

	def __str__(self):
		return 'buf=%s\nnpos=%s' % (str(list(map(str, self.buf[0:self.size]))), str(self.npos))
(N, E) = map(int, input().split(' '))
V = [[] for _ in range(N + 1)]
for _ in range(E):
	(u, v, w) = map(int, input().split(' '))
	(V[u].append((v, w)), V[v].append((u, w)))
(H, M, rs) = (MinHeap(N), [10 ** 9] * (N + 1), 'NO PATH EXISTS')
H.push(Node(1, 0))
M[1] = 0
while H.size:
	c = H.pop()
	if c.id == N:
		rs = str(c.key)
		break
	for (x, w) in V[c.id]:
		cw = c.key if c.key > w else w
		if M[x] > cw:
			M[x] = cw
			qx = H.getById(x)
			if qx == None:
				H.push(Node(x, cw))
			else:
				H.replace(Node(x, cw))
print(rs)


import sys
from collections import defaultdict
from collections import deque
import heapq

def min_path(graph, n):
	costs = [10 ** 10] * (n + 1)
	work = []
	heapq.heappush(work, (0, 1))
	costs[1] = 0
	while work:
		(current_cost, current_node) = heapq.heappop(work)
		for (neighbour, cost) in graph[current_node]:
			acc_cost = max(current_cost, cost)
			if acc_cost < costs[neighbour]:
				costs[neighbour] = acc_cost
				heapq.heappush(work, (acc_cost, neighbour))
	return costs[n] if costs[n] < 10 ** 10 else 'NO PATH EXISTS'
(g_nodes, g_edges) = map(int, input().split())
graph = defaultdict(set)
for _ in range(g_edges):
	(start, end, cost) = map(int, input().split())
	graph[start].add((end, cost))
	graph[end].add((start, cost))
print(min_path(graph, g_nodes))


import sys

def lowestCost(graph):
	n = len(graph)
	g_costs = [None for _ in range(n)]
	g_costs[0] = 0
	ws = dict()
	ws[0] = 0
	for (cost, node) in graph[0]:
		ws[node] = cost
	while len(ws) > 0:
		(node, cost) = ws.popitem()
		if g_costs[node] == None or g_costs[node] > cost:
			g_costs[node] = cost
			for (c, new_n) in graph[node]:
				new_c = max(c, cost)
				if g_costs[new_n] == None or g_costs[new_n] > new_c:
					if not new_n in ws or ws[new_n] > new_c:
						ws[new_n] = new_c
	if g_costs[n - 1] == None:
		return 'NO PATH EXISTS'
	else:
		return g_costs[n - 1]
(n, m) = [int(i) for i in input().strip().split()]
graph = [[] for _ in range(n)]
for _ in range(m):
	(i, j, cost) = [int(edges_temp) for edges_temp in input().strip().split()]
	i -= 1
	j -= 1
	graph[i].append((cost, j))
	graph[j].append((cost, i))
print(lowestCost(graph))


(n, m) = [int(x) for x in input().split()]
graph = [[] for _ in range(n)]
for _ in range(m):
	(u, v, c) = [int(x) for x in input().split()]
	u -= 1
	v -= 1
	graph[u].append((v, c))
	graph[v].append((u, c))
import heapq
heap = [(0, 0)]
seen = set()
while len(heap) > 0:
	(c, v) = heapq.heappop(heap)
	if v == n - 1:
		print(c)
		exit(0)
		break
	if v in seen:
		continue
	seen.add(v)
	for (u, c1) in graph[v]:
		if u not in seen:
			heapq.heappush(heap, (c + max(0, c1 - c), u))
print('NO PATH EXISTS')