Alex is very fond of traveling. There are n cities, labeled from 1 to n.  You are also given flights, a list of travel flights as directed weighted edges flights[i] = (u_{i},v_{i},w_{i}) where u_{i }is the source node, v_{i} is the target node, and w_{i} is the price it takes for a person to travel from source to target.
Currently, Alex is in k'th city and wants to visit one city of his choice. Return the minimum money Alex should have so that he can visit any city of his choice from k'th city. If there is a city that has no path from k'th city, which means Alex can't visit that city, return -1. 
Alex always takes the optimal path. He can any city via another city by taking multiple flights.
 
Example 1:
Input:
n: 4
k: 2
flights size: 3
flights: [[2,1,1],[2,3,1],[3,4,1]]
Output:
2
Explanation:
to visit 1 from 2 takes cost 1
to visit 2 from 2 takes cost 0
to visit 3 from 2 takes cost 1
to visit 4 from 2 takes cost 2,
2->3->4
So if Alex wants to visit city 4
from 2, he needs 2 units of money
Example 2:
Input:
n: 4 
k: 3 
flights size: 3 
flights: [[2,1,1],[2,3,1],[3,4,1]] 
Output: -1
Explanation:
There is no direct or indirect path 
to visit city 2 and 1 from city 3
Your Task:
You don't need to print or input anything. Complete the function minimumCost() which takes a  flights array, an integer n and an integer k as the input parameters and returns an integer, denoting the minimum money Alex should have so that he can visit any city of his choice from k'th city.
Expected Time Complexity: O((V+E) log V), here V is number of cities and E is number of flights. 
Expected Auxiliary Space: O(V+E), here V is number of cities and E is number of flights. 
Constraints:
2 <= n <= 500
1 <= flights.length <= 100000
flights[i].length == 3
1 <= u_{i}, v_{i}, k<= n
u_{i} != v_{i}
1 <= w_{i} <= 100
All the pairs (u_{i}, v_{i}) are unique. (i.e., no multiple edges)

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Starter code: #User function Template for python3



from typing import List

class Solution:

    def minimumCost(self, flights: List[List[int]], n : int, k : int) -> int:

        # code here

        

Solutions:
import numpy as np
from collections import defaultdict
from collections import deque
from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		g = defaultdict(list)
		for (s, d, w) in flights:
			g[s].append((d, w))
		costs = [np.inf] * (n + 1)
		costs[k] = 0
		costs[0] = 0
		q = deque([k])
		while q:
			cur = q.popleft()
			for (nbr, w) in g[cur]:
				ncost = costs[cur] + w
				if costs[nbr] > ncost:
					costs[nbr] = ncost
					q.append(nbr)
		s = max(costs)
		return -1 if s == np.inf else s


import heapq
from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		dis = [float('inf') for _ in range(n)]
		dis[k - 1] = 0
		pq = [(0, k - 1)]
		adj = [[] for _ in range(n)]
		for (u, v, w) in flights:
			adj[u - 1].append([v - 1, w])
		while pq:
			(d, u) = heapq.heappop(pq)
			for (v, w) in adj[u]:
				if w + d < dis[v]:
					dis[v] = w + d
					heapq.heappush(pq, (dis[v], v))
		maximum = max(dis)
		return -1 if maximum == float('inf') else maximum


import heapq
from collections import defaultdict
from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		grph = defaultdict(dict)
		for (x, y, w) in flights:
			grph[x][y] = w
		vis = set()
		hp = []
		vis.add(k)
		for i in grph[k]:
			heapq.heappush(hp, [grph[k][i], i])
		ans = [0]
		while hp:
			p = heapq.heappop(hp)
			if p[1] not in vis:
				vis.add(p[1])
				ans[0] = max(ans[0], p[0])
				for i in grph[p[1]]:
					heapq.heappush(hp, [p[0] + grph[p[1]][i], i])
		if len(vis) == n:
			return ans[0]
		return -1


from typing import List
import heapq

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		graph = [[] for _ in range(n + 1)]
		for (start, end, cost) in flights:
			graph[start].append((end, cost))
		dis = [float('inf')] * (n + 1)
		dis[k] = 0
		queue = [(0, k)]
		while queue:
			(cost, root) = heapq.heappop(queue)
			for (node, wt) in graph[root]:
				if dis[node] > cost + wt:
					dis[node] = cost + wt
					heapq.heappush(queue, (cost + wt, node))
		return max(dis[1:]) if max(dis[1:]) != float('inf') else -1


from typing import List
from collections import defaultdict
from heapq import heappush, heappop

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		graph = defaultdict(list)
		for (u, v, w) in flights:
			graph[u - 1].append([v - 1, w])
		distance = [float('inf')] * n
		heap = []
		heappush(heap, [0, k - 1])
		distance[k - 1] = 0
		while heap:
			(curr_dist, node) = heappop(heap)
			for (next_node, weight) in graph[node]:
				if curr_dist + weight < distance[next_node]:
					heappush(heap, [curr_dist + weight, next_node])
					distance[next_node] = curr_dist + weight
		maxi = max(distance)
		if maxi == float('inf'):
			return -1
		return maxi


from collections import deque
from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		flight_map = {}
		for (src, dest, wt) in flights:
			if src in flight_map:
				flight_map[src].append((dest, wt))
			else:
				flight_map[src] = [(dest, wt)]
		queue = deque([(k, 0)])
		ans = [float('inf') for _ in range(n + 1)]
		ans[0] = 0
		while queue:
			(curr_city, wt) = queue.popleft()
			if wt < ans[curr_city]:
				ans[curr_city] = wt
				if curr_city in flight_map:
					for nc in flight_map[curr_city]:
						queue.append((nc[0], nc[1] + wt))
		if max(ans) == float('inf'):
			return -1
		return max(ans)


from queue import PriorityQueue
from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		adj = [[] for i in range(n + 1)]
		for i in flights:
			adj[i[0]].append((i[1], i[2]))
		dist = [1000000000.0] * (n + 1)
		dist[k] = 0
		pq = PriorityQueue()
		pq.put((0, k))
		while not pq.empty():
			it = pq.get()
			node = it[1]
			cost = it[0]
			for i in adj[node]:
				adjnode = i[0]
				edw = i[1]
				if cost + edw < dist[adjnode]:
					dist[adjnode] = cost + edw
					pq.put((cost + edw, adjnode))
		for i in range(n + 1):
			if i > 0 and dist[i] == 1000000000.0:
				return -1
		return max(dist[1:])


from collections import defaultdict
from typing import List
import heapq

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		q = [(0, k)]
		adj = defaultdict(list)
		dist = {}
		for (u, v, w) in flights:
			adj[u].append((v, w))
		while q:
			(dis, node) = heapq.heappop(q)
			if node not in dist:
				dist[node] = dis
				for (nei, weight) in adj[node]:
					heapq.heappush(q, (dis + weight, nei))
		return max(dist.values()) if len(dist) == n else -1


from typing import List
import heapq

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		adj = [[] for i in range(n + 1)]
		dist = [1000000000.0] * (n + 1)
		dist[k] = 0
		maxi = 0
		for i in range(len(flights)):
			adj[flights[i][0]].append((flights[i][1], flights[i][2]))
		pq = []
		heapq.heapify(pq)
		heapq.heappush(pq, (0, k))
		while pq:
			(time, node) = heapq.heappop(pq)
			for p in adj[node]:
				(n, t) = p
				if dist[n] > time + t:
					dist[n] = time + t
					heapq.heappush(pq, (dist[n], n))
		for i in dist[1:]:
			if i == 1000000000.0:
				return -1
			maxi = max(maxi, i)
		return maxi


import heapq as h
from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		adj = [[] for i in range(n)]
		for ele in flights:
			adj[ele[0] - 1].append([ele[1], ele[2]])
		distance = [float('inf') for i in range(n + 1)]
		distance[k] = 0
		distance[0] = 0
		q = []
		q.append([0, k])
		while q:
			(dis, node) = h.heappop(q)
			for child in adj[node - 1]:
				if dis + child[1] < distance[child[0]]:
					distance[child[0]] = dis + child[1]
					h.heappush(q, [distance[child[0]], child[0]])
		m = 0
		for ele in distance:
			m = max(ele, m)
		if m == float('inf'):
			return -1
		return m


import heapq
from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		adj = [[] for i in range(n + 1)]
		for i in flights:
			adj[i[0]].append([i[1], i[2]])
		dist = [float('inf')] * (n + 1)
		dist[k] = 0
		pq = [[0, k]]
		while pq:
			item = heapq.heappop(pq)
			dest = item[0]
			node = item[1]
			for i in adj[node]:
				vert = i[0]
				wt = i[1]
				if dest + wt < dist[vert]:
					dist[vert] = dest + wt
					heapq.heappush(pq, [dest + wt, vert])
		for i in range(1, len(dist)):
			if dist[i] == float('inf'):
				return -1
		return max(dist[1:])


import heapq
from typing import List

class Solution:

	def minimumCost(self, times: List[List[int]], n: int, k: int) -> int:
		adj_list = [[] for _ in range(n + 1)]
		for i in range(len(times)):
			src = times[i][0]
			dst = times[i][1]
			cost = times[i][2]
			adj_list[src].append([dst, cost])
		hp = []
		dp = [float('inf') for _ in range(n + 1)]
		dp[k] = 0
		heapq.heappush(hp, (0, k))
		while hp:
			(time, node) = heapq.heappop(hp)
			for nei in adj_list[node]:
				adjel = nei[0]
				cost = nei[1]
				if dp[adjel] > cost + time:
					dp[adjel] = cost + time
					heapq.heappush(hp, (cost + time, adjel))
		if max(dp[1:]) == float('inf'):
			return -1
		else:
			return max(dp[1:])


from typing import List
import heapq

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		adj = [[] for _ in range(n + 1)]
		for (u, v, price) in flights:
			adj[u].append((v, price))
		dist = [float('inf')] * (n + 1)
		dist[0] = 0
		dist[k] = 0
		pq = [(0, k)]
		while pq:
			(dis, node) = heapq.heappop(pq)
			for (adjNode, edgeWt) in adj[node]:
				if dist[adjNode] > dis + edgeWt:
					dist[adjNode] = dis + edgeWt
					heapq.heappush(pq, (dist[adjNode], adjNode))
		res = max(dist)
		return res if res != float('inf') else -1


from heapq import heappop, heappush
from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		adj = [[] for i in range(n + 1)]
		for i in flights:
			adj[i[0]].append([i[1], i[2]])
		money = [float('inf') for i in range(n + 1)]
		q = []
		q.append([0, k])
		money[k] = 0
		while q:
			top = heappop(q)
			mon = top[0]
			node = top[1]
			for i in adj[node]:
				if mon + i[1] < money[i[0]]:
					money[i[0]] = mon + i[1]
					heappush(q, [money[i[0]], i[0]])
		money[0] = -1
		ans = max(money)
		if ans == float('inf'):
			return -1
		return ans


from typing import *
import heapq

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int):
		adj = [[] for _ in range(n)]
		for flight in flights:
			adj[flight[0] - 1].append((flight[1] - 1, flight[2]))
		distance = [float('inf') for _ in range(n)]
		distance[k - 1] = 0
		pq = []
		heapq.heappush(pq, (0, k - 1))
		while len(pq) > 0:
			(dist, source) = heapq.heappop(pq)
			for (neigh, weigh) in adj[source]:
				if distance[neigh] > dist + weigh:
					distance[neigh] = dist + weigh
					heapq.heappush(pq, (distance[neigh], neigh))
		for i in range(n):
			if distance[i] == float('inf'):
				distance[i] = -1
				return -1
		ans = -1
		return max(distance)


from collections import defaultdict
from queue import PriorityQueue
from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		g = defaultdict(list)
		for (u, v, w) in flights:
			g[u].append((v, w))
		q = PriorityQueue()
		q.put((0, k))
		time_taken = [100000 for _ in range(n + 1)]
		time_taken[k] = 0
		while not q.empty():
			(time, at) = q.get()
			for (neigh, t) in g[at]:
				if time_taken[at] + t < time_taken[neigh]:
					time_taken[neigh] = time_taken[at] + t
					q.put((time_taken[at] + t, neigh))
		for i in range(1, n + 1):
			if time_taken[i] == 100000:
				return -1
		return max(time_taken[1:])


from typing import List
from collections import defaultdict
import heapq

class Solution:

	def minimumCost(self, times: List[List[int]], n: int, k: int) -> int:
		adjlist = defaultdict(list)
		for i in times:
			u = i[0]
			v = i[1]
			wt = i[2]
			adjlist[u].append([v, wt])
		minheap = [(0, k)]
		visited = set()
		t = 0
		while minheap:
			(wt1, n1) = heapq.heappop(minheap)
			if n1 in visited:
				continue
			t = max(wt1, t)
			visited.add(n1)
			for (n2, wt2) in adjlist[n1]:
				heapq.heappush(minheap, (wt1 + wt2, n2))
		if len(visited) == n:
			return t
		else:
			return -1


from collections import defaultdict
from collections import deque
from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		g = defaultdict(list)
		for (s, d, w) in flights:
			g[s].append((d, w))
		costs = [float('INF')] * (n + 1)
		costs[k] = 0
		costs[0] = 0
		q = deque([k])
		while q:
			cur = q.popleft()
			for (nbr, w) in g[cur]:
				ncost = costs[cur] + w
				if costs[nbr] > ncost:
					costs[nbr] = ncost
					q.append(nbr)
		s = max(costs)
		return -1 if s == float('Inf') else s


import heapq

def shortestPath(adj, src):
	V = len(adj)
	pq = []
	heapq.heappush(pq, (0, src))
	dist = [1 << 32] * V
	dist[src] = 0
	while pq:
		(d, u) = heapq.heappop(pq)
		for (v, weight) in adj[u]:
			if dist[v] > dist[u] + weight:
				dist[v] = dist[u] + weight
				heapq.heappush(pq, (dist[v], v))
	m = 0
	for i in range(1, len(dist)):
		if dist[i] == 1 << 32:
			return -1
		m = max(m, dist[i])
	return m
from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		graph = [[] for i in range(n + 1)]
		for i in flights:
			graph[i[0]].append((i[1], i[2]))
		return shortestPath(graph, k)


import collections
from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		adj_list = collections.defaultdict(list)
		for (u, v, w) in flights:
			adj_list[u].append((v, w))
		dist = [-1 for _ in range(n + 1)]
		q = collections.deque()
		dist[k] = 0
		q.append((k, dist[k]))
		ans = -1
		while q:
			curr = q.popleft()
			node = curr[0]
			cost = curr[1]
			for neighbour in adj_list[node]:
				new_node = neighbour[0]
				new_cost = neighbour[1]
				if dist[new_node] == -1:
					dist[new_node] = cost + new_cost
					q.append((new_node, dist[new_node]))
				elif dist[new_node] > cost + new_cost:
					dist[new_node] = cost + new_cost
					q.append((new_node, dist[new_node]))
		for d in range(1, len(dist)):
			if dist[d] != -1:
				ans = max(ans, dist[d])
			else:
				return -1
		return ans


from heapq import *
from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		graph = {i: [] for i in range(1, n + 1)}
		for flight in flights:
			(source, target, time) = flight
			graph[source].append((time, target))
		res = 0
		min_heap = [(0, k)]
		visited = set()
		while min_heap:
			(min_time, node) = heappop(min_heap)
			if node in visited:
				continue
			visited.add(node)
			res = min_time
			neighbors = graph[node]
			for neighbor in neighbors:
				(n_time, n_node) = neighbor
				if n_node not in visited:
					heappush(min_heap, (n_time + min_time, n_node))
		return res if len(visited) == n else -1


from typing import List
import heapq
from collections import defaultdict

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		adj = defaultdict(list)
		for time in flights:
			adj[time[0]].append([time[1], time[2]])
		heap = []
		dist = [float('inf')] * (n + 1)
		dist[k] = 0
		heapq.heappush(heap, [0, k])
		while heap:
			(dis, node) = heapq.heappop(heap)
			for eg in adj[node]:
				adjNode = eg[0]
				egW = eg[1]
				if dis + egW < dist[adjNode]:
					dist[adjNode] = dis + egW
					heapq.heappush(heap, [dis + egW, adjNode])
		ans = -999
		for i in range(1, n + 1):
			if dist[i] == float('inf'):
				return -1
			if dist[i] > ans:
				ans = dist[i]
		return ans


from typing import List
import heapq

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		min_cost = [-1 for i in range(n)]
		min_cost[k - 1] = 0
		adj = [[] for i in range(n)]
		for (u, v, w) in flights:
			adj[u - 1].append((w, v - 1))
		q = [v for v in adj[k - 1]]
		heapq.heapify(q)
		while q:
			(w, v) = heapq.heappop(q)
			if min_cost[v] != -1:
				continue
			min_cost[v] = w
			for (w1, v1) in adj[v]:
				heapq.heappush(q, (w + w1, v1))
		if min(min_cost) == -1:
			return -1
		return max(min_cost)


from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		from collections import defaultdict
		d = defaultdict(list)
		for (i, j, w) in flights:
			d[i].append((j, w))
		cost = [float('inf')] * (n + 1)
		cost[k] = 0
		queue = []
		queue.append(k)
		while queue:
			curr = queue.pop(0)
			for (j, w) in d[curr]:
				if cost[j] > cost[curr] + w:
					queue.append(j)
					cost[j] = cost[curr] + w
		ans = 0
		for i in range(1, n + 1):
			ans = max(ans, cost[i])
		if ans == float('inf'):
			return -1
		else:
			return ans


from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		import heapq
		dist = [1000000000.0] * (n + 1)
		adj = [[] for i in range(n + 1)]
		for i in flights:
			adj[i[0]].append([i[1], i[2]])
		dist[k] = 0
		q = []
		heapq.heappush(q, [0, k])
		while len(q):
			a = heapq.heappop(q)
			dis = a[0]
			s = a[1]
			for i in adj[s]:
				d = i[1]
				new = i[0]
				if dist[new] > dis + d:
					dist[new] = dis + d
					heapq.heappush(q, [dist[new], new])
		maxx = -1
		for i in range(1, len(dist)):
			if dist[i] == 1000000000.0:
				return -1
			elif maxx < dist[i]:
				maxx = dist[i]
		return maxx


from queue import Queue
from typing import List
import heapq

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		cost = [1000000000.0] * (n + 1)
		next_citys = [[] for _ in range(n + 1)]
		for flight in flights:
			u = flight[0]
			v = flight[1]
			w = flight[2]
			next_citys[u].append([v, w])
		travel = list()
		travel = Queue()
		travel.put(k)
		cost[k] = 0
		while not travel.empty():
			current_city = travel.get()
			for next_city in next_citys[current_city]:
				if cost[next_city[0]] > cost[current_city] + next_city[1]:
					cost[next_city[0]] = cost[current_city] + next_city[1]
					travel.put(next_city[0])
		my_cost = max(cost[1:])
		if my_cost == 1000000000.0:
			return -1
		else:
			return my_cost


from queue import Queue
from typing import List
import heapq

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		cost = [1000000000.0] * (n + 1)
		next_citys = [[] for _ in range(n + 1)]
		for flight in flights:
			u = flight[0]
			v = flight[1]
			w = flight[2]
			next_citys[u].append([v, w])
		travel = list()
		heapq.heappush(travel, (0, k))
		cost[k] = 0
		while travel:
			(dist, current_city) = heapq.heappop(travel)
			if cost[current_city] < dist:
				continue
			for next_city in next_citys[current_city]:
				if cost[next_city[0]] > cost[current_city] + next_city[1]:
					cost[next_city[0]] = cost[current_city] + next_city[1]
					heapq.heappush(travel, (cost[next_city[0]], next_city[0]))
		my_cost = max(cost[1:])
		if my_cost == 1000000000.0:
			return -1
		else:
			return my_cost


from typing import List
from collections import deque
import heapq

class Solution:

	def __init__(self):
		self.graph = dict()
		self.visited = dict()

	def add_edge(self, edge):
		(src, dest, wt) = edge
		lst = self.graph.get(src, [])
		lst.append([dest, wt])
		self.graph[src] = lst

	def minimumCost(self, flights, n, k):
		for i in range(1, n + 1):
			self.visited[i] = None
		for flight in flights:
			self.add_edge(flight)
		return self.bfs(k)

	def bfs(self, src):
		q = list()
		level = 0
		heapq.heappush(q, [0, src])
		while len(q) > 0:
			(level, ele) = heapq.heappop(q)
			if self.visited.get(ele, None) is None:
				self.visited[ele] = level
			else:
				continue
			for node in self.graph.get(ele, []):
				(nbr, wt) = node
				heapq.heappush(q, [level + wt, nbr])
		maxa = 0
		for k in self.visited.keys():
			if self.visited[k] == None:
				return -1
			else:
				maxa = max(maxa, self.visited[k])
		return maxa


from typing import List
from collections import defaultdict
import sys
import heapq

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		graph = defaultdict(dict)
		for item in flights:
			(u, v, cost) = item
			graph[u][v] = cost
		distance = {u: sys.maxsize for u in range(1, n + 1)}
		distance[k] = 0
		visited = [False for u in range(0, n + 1)]
		q = []
		heapq.heappush(q, (0, k))
		while q:
			(dist, u) = heapq.heappop(q)
			visited[u] = True
			for v in graph[u]:
				if visited[v] == False:
					newdist = dist + graph[u][v]
					if newdist < distance[v]:
						distance[v] = newdist
						heapq.heappush(q, (newdist, v))
		ans = max(distance.values())
		if ans != sys.maxsize:
			return ans
		else:
			return -1


from typing import List
import heapq

class Solution:

	def dijkstra(self, source, adj, V):
		dist = [1000000000000.0 for size in range(V + 1)]
		queue = [[0, source]]
		dist[source] = 0
		while len(queue):
			(d, u) = heapq.heappop(queue)
			if dist[u] < d:
				continue
			for (v, w) in adj[u]:
				if dist[u] + w < dist[v]:
					dist[v] = dist[u] + w
					heapq.heappush(queue, [dist[v], v])
		return dist

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		adj = [[] for size in range(n + 1)]
		for (u, v, w) in flights:
			adj[u].append([v, w])
		dist = self.dijkstra(k, adj, n)
		result = 0
		for i in range(1, n + 1):
			if i == k:
				continue
			if dist[i] == 1000000000000.0:
				return -1
			else:
				result = max(result, dist[i])
		return result


from collections import defaultdict, deque
import math
from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		flightMap = defaultdict(list)
		for flight in flights:
			flightMap[flight[0]].append(flight)
		costArr = [math.inf] * (n + 1)
		costArr[k] = 0
		visitingArr = deque([[k, k, 0]])
		while visitingArr:
			(source, target, cost) = visitingArr.popleft()
			if costArr[target] > costArr[source] + cost or source == target:
				costArr[target] = costArr[source] + cost
				visitingArr.extend(flightMap[target])
		maxCost = max(costArr[1:])
		return -1 if maxCost == math.inf else maxCost


from typing import List
import heapq

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		graph = {}
		for f in flights:
			if f[0] not in graph:
				graph[f[0]] = {}
			new_pairs = {f[1]: f[2]}
			graph[f[0]].update(new_pairs)
		distances = {i + 1: float('inf') for i in range(n)}
		distances[k] = 0
		queue = []
		heapq.heappush(queue, [distances[k], k])
		visited = set()
		while queue:
			(current_distance, vertex) = heapq.heappop(queue)
			if vertex in visited:
				continue
			visited.add(vertex)
			if vertex in graph:
				for (neighbor, cost) in graph[vertex].items():
					distance = current_distance + cost
					if distance < distances[neighbor]:
						distances[neighbor] = distance
						heapq.heappush(queue, [distance, neighbor])
		result = 0
		for c in distances.values():
			if c == float('inf'):
				return -1
			result = max(c, result)
		return result


import heapq
from collections import defaultdict
from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		adj = defaultdict(list)
		for it in flights:
			adj[it[0]].append((it[1], it[2]))
		dist = [1000000000.0] * (n + 1)
		dist[k] = 0
		pq = []
		heapq.heappush(pq, (0, k))
		while pq:
			(cost, node) = heapq.heappop(pq)
			for it in adj[node]:
				(adnode, edw) = it
				if cost + edw < dist[adnode]:
					dist[adnode] = cost + edw
					heapq.heappush(pq, (cost + edw, adnode))
		for i in range(1, n + 1):
			if dist[i] == 1000000000.0:
				return -1
		return max(dist[1:])


from typing import List

class Solution:

	def fun(self, mn, node, arr, visited, cost):
		visited.add(node)
		if cost < arr[node]:
			arr[node] = cost
			for num in mn[node]:
				if num[0] not in visited:
					arr = self.fun(mn, num[0], arr, visited, cost + num[1])
		visited.remove(node)
		return arr

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		arr = [float('inf')] * (n + 1)
		arr[k] = arr[0] = 0
		mn = {x: [] for x in range(1, n + 1)}
		for num in flights:
			mn[num[0]].append((num[1], num[2]))
		q = [k]
		while q:
			curr = q.pop(0)
			for num in mn[curr]:
				if arr[curr] + num[1] < arr[num[0]]:
					q.append(num[0])
					arr[num[0]] = arr[curr] + num[1]
		res = max(arr)
		if res == float('inf'):
			return -1
		return res


import heapq
import sys
from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		V = n
		S = k
		adj = [[] for _ in range(n + 1)]
		for i in flights:
			adj[i[0]].append([i[1], i[2]])
		minheap = []
		dist = [sys.maxsize for _ in range(V + 1)]
		heapq.heappush(minheap, [0, S])
		dist[S] = 0
		while len(minheap) != 0:
			top = heapq.heappop(minheap)
			dis = top[0]
			node = top[1]
			for it in adj[node]:
				edgewei = it[1]
				adjnode = it[0]
				if dis + edgewei < dist[adjnode]:
					dist[adjnode] = dis + edgewei
					heapq.heappush(minheap, [dist[adjnode], adjnode])
		for i in range(1, len(dist)):
			if dist[i] == sys.maxsize:
				return -1
		return max(dist[1:])


from typing import List
from collections import defaultdict

def update_discovered(discovered_list, discovered_dict, entry):
	(dest, new_cost) = entry
	(new_idx, old_idx) = (None, None)
	old_cost = None
	if dest in discovered_dict:
		old_idx = discovered_dict[dest]
		old_cost = discovered_list[old_idx][1]
		assert new_cost < discovered_list[old_idx][1]
		del discovered_list[old_idx]
	(min_i, max_i) = (0, len(discovered_list))
	while min_i < max_i:
		mid_i = (min_i + max_i) // 2
		if new_cost > discovered_list[mid_i][1]:
			max_i = mid_i
		elif new_cost < discovered_list[mid_i][1]:
			min_i = mid_i + 1
		else:
			(min_i, max_i) = (mid_i, mid_i)
	assert min_i == max_i
	new_idx = min_i
	discovered_list.insert(new_idx, entry)
	if old_idx is None:
		old_idx = len(discovered_list) - 1
	for i in range(min(old_idx, new_idx), max(old_idx, new_idx) + 1):
		discovered_dict[discovered_list[i][0]] = i

def my_answer(flights, n, k):
	flights_dict = defaultdict(dict)
	for (source, dest, cost) in flights:
		flights_dict[source][dest] = cost
	unprocessed = set(range(1, n + 1))
	processed = {}
	discovered_list = []
	discovered_dict = {}
	max_path_cost = 0
	unprocessed.remove(k)
	discovered_list.append((k, 0))
	discovered_dict[k] = 0
	while discovered_list:
		(cheapest_city, cheapest_path_cost) = discovered_list.pop()
		del discovered_dict[cheapest_city]
		assert cheapest_city not in processed
		flights_out = flights_dict[cheapest_city]
		for (dest, flight_cost) in flights_out.items():
			path_cost_to_dest = cheapest_path_cost + flight_cost
			if dest in processed:
				assert processed[dest] <= path_cost_to_dest
				continue
			elif dest in discovered_dict:
				discovered_idx = discovered_dict[dest]
				if path_cost_to_dest < discovered_list[discovered_idx][1]:
					update_discovered(discovered_list, discovered_dict, (dest, path_cost_to_dest))
				else:
					pass
			else:
				update_discovered(discovered_list, discovered_dict, (dest, path_cost_to_dest))
				unprocessed.remove(dest)
		processed[cheapest_city] = cheapest_path_cost
		max_path_cost = max(max_path_cost, cheapest_path_cost)
	if len(unprocessed) > 0:
		return -1
	else:
		return max_path_cost

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		return my_answer(flights, n, k)


import heapq
from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		adj = [[] for i in range(n + 1)]
		for (u, v, w) in flights:
			adj[u].append((v, w))
		push = heapq.heappush
		pop = heapq.heappop
		pq = []
		cost = [float('inf')] * (n + 1)
		push(pq, (0, k))
		cost[k] = cost[0] = 0
		while pq:
			(wt, node) = pop(pq)
			for (adjNode, adjWt) in adj[node]:
				if wt + adjWt < cost[adjNode]:
					cost[adjNode] = wt + adjWt
					push(pq, (wt + adjWt, adjNode))
		mx = 0
		for i in cost:
			mx = max(mx, i)
		return mx if mx != float('inf') else -1


from typing import List
import heapq

class Solution:

	def createAdjList(self, flights):
		adj_list = {}
		for (src, dest, cost) in flights:
			if src not in adj_list:
				adj_list[src] = [(dest, cost)]
			else:
				adj_list[src].append((dest, cost))
		return adj_list

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		node_list = []
		heapq.heappush(node_list, (0, k))
		min_cost = 0
		visited = set()
		adj_list = self.createAdjList(flights)
		while len(node_list) > 0:
			(node_cost, node) = heapq.heappop(node_list)
			if node not in visited:
				visited.add(node)
				min_cost = max(min_cost, node_cost)
				for (neighbor, neighbor_cost) in adj_list.get(node, []):
					if neighbor not in visited:
						heapq.heappush(node_list, (node_cost + neighbor_cost, neighbor))
		return min_cost if len(visited) == n else -1


import sys
from typing import List
from collections import deque, defaultdict

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		maxi = sys.maxsize
		dist = [maxi] * (n + 1)
		dist[k] = dist[0] = 0
		adj = defaultdict(list)
		for (u, v, w) in flights:
			adj[u].append([v, w])
		que = deque([k])
		while que:
			node = que.popleft()
			for adjacent in adj[node]:
				(u, v, w) = (node, adjacent[0], adjacent[1])
				if dist[v] > dist[u] + w:
					dist[v] = dist[u] + w
					que.append(v)
		return max(dist) if max(dist) != maxi else -1


import collections
from typing import List

class Solution:

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		adj_li = collections.defaultdict(list)
		for (u, v, w) in flights:
			adj_li[u].append((v, w))
		dist = [-1 for _ in range(n + 1)]
		q = collections.deque()
		dist[k] = 0
		q.append((k, dist[k]))
		ans = -1
		while q:
			curr = q.popleft()
			no = curr[0]
			co = curr[1]
			for neighbour in adj_li[no]:
				new_no = neighbour[0]
				new_co = neighbour[1]
				if dist[new_no] == -1:
					dist[new_no] = co + new_co
					q.append((new_no, dist[new_no]))
				elif dist[new_no] > co + new_co:
					dist[new_no] = co + new_co
					q.append((new_no, dist[new_no]))
		for d in range(1, len(dist)):
			if dist[d] != -1:
				ans = max(ans, dist[d])
			else:
				return -1
		return ans


import sys
import heapq
from typing import List

class Solution:

	def dijkstra(self, adjList, dis, source):
		dis[source] = 0
		hq = []
		heapq.heapify(hq)
		heapq.heappush(hq, [0, source])
		while hq:
			curr = heapq.heappop(hq)
			for i in range(len(adjList[curr[1]])):
				nei = adjList[curr[1]][i]
				if dis[nei[0]] > dis[curr[1]] + nei[1]:
					dis[nei[0]] = dis[curr[1]] + nei[1]
					heapq.heappush(hq, [dis[nei[0]], nei[0]])

	def minimumCost(self, flights: List[List[int]], n: int, k: int) -> int:
		adjList = [[] for i in range(n + 1)]
		for i in range(len(flights)):
			v = flights[i][0]
			u = flights[i][1]
			w = flights[i][2]
			adjList[v].append([u, w])
		dis = [sys.maxsize for i in range(n + 1)]
		self.dijkstra(adjList, dis, k)
		res = 0
		for i in range(1, n + 1):
			res = max(res, dis[i])
		return -1 if res == sys.maxsize else res