Given a Directed Acyclic Graph of N vertices from 0 to N-1 and a 2D Integer array(or vector) edges[ ][ ] of length M, where there is a directed edge from edge[i][0] to edge[i][1] with a distance of edge[i][2] for all i, 0<=i
Find the shortest path from src(0) vertex to all the vertices and if it is impossible to reach any vertex, then return -1 for that vertex.
 
Example:
Input:
n = 6, m= 7
edge=[[0,1,2],[0,4,1],[4,5,4]
,[4,2,2],[1,2,3],[2,3,6],[5,3,1]]
Output:
0 2 3 6 1 5
 
Your Task:
You don't need to print or input anything. Complete the function shortest path() which takes an integer N as number of vertices, an integer M as number of edges and a 2D Integer array(or vector) edges as the input parameters and returns an integer array(or vector), denoting the list of distance from src to all nodes.
 
Constraint:
	1 <= n,m <= 100
	0 <= edge_{i,0},edge_{i,1} < n
	 
 
Expected Time Complexity: O(N+E), where N is the number of nodes and E is edges
Expected Space Complexity: O(N)

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Shortest paths

Starter code: #User function Template for python3



from typing import List



class Solution:

    def shortestPath(self, n : int, m : int, edges : List[List[int]]) -> List[int]:

        pass

Solutions:
from typing import List
import math

class Solution1:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		distance = [100000] * n
		distance[0] = 0
		for i in range(n - 1):
			for edge in edges:
				u = edge[0]
				v = edge[1]
				w = edge[2]
				if distance[u] + w < distance[v]:
					distance[v] = distance[u] + w
		for i in range(len(distance)):
			if distance[i] == 100000:
				distance[i] = -1
		return distance
from queue import deque
from typing import List

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		q = deque()
		ind = {}
		for i in range(n):
			ind[i] = 0
		adj = [[] for i in range(n)]
		for edge in edges:
			adj[edge[0]].append([edge[1], edge[2]])
		for e in edges:
			ind[e[1]] += 1
		for i in ind:
			if ind[i] == 0:
				q.append(i)
		ans = deque()
		while q:
			x = q.popleft()
			ans.append(x)
			for nbr in adj[x]:
				ind[nbr[0]] -= 1
				if ind[nbr[0]] == 0:
					q.append(nbr[0])
		dist = [math.inf] * n
		dist[0] = 0
		while ans:
			node = ans.popleft()
			for e in adj[node]:
				if dist[node] + e[1] < dist[e[0]]:
					dist[e[0]] = dist[node] + e[1]
		for i in range(len(dist)):
			if dist[i] == math.inf:
				dist[i] = -1
		return dist


from typing import List

class Solution1:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		dist = [100000] * n
		dist[0] = 0
		for i in range(n - 1):
			for e in edges:
				u = e[0]
				v = e[1]
				w = e[2]
				if dist[u] + w < dist[v]:
					dist[v] = dist[u] + w
		for i in range(len(dist)):
			if dist[i] == 100000:
				dist[i] = -1
		return dist
from queue import deque

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = [[] for _ in range(n)]
		for e in edges:
			adj[e[0]].append([e[1], e[2]])
		indegree = {}
		for i in range(n):
			indegree[i] = 0
		for e in edges:
			indegree[e[1]] += 1
		q = deque()
		topo = deque()
		for d in indegree:
			if indegree[d] == 0:
				q.append(d)
		while q:
			node = q.popleft()
			topo.append(node)
			for nbr in adj[node]:
				indegree[nbr[0]] -= 1
				if indegree[nbr[0]] == 0:
					q.append(nbr[0])
		dist = [100000] * n
		dist[0] = 0
		while topo:
			x = topo.popleft()
			for nbr in adj[x]:
				u = x
				v = nbr[0]
				w = nbr[1]
				if dist[u] + w < dist[v]:
					dist[v] = dist[u] + w
		for d in range(len(dist)):
			if dist[d] == 100000:
				dist[d] = -1
		return dist


from typing import List
import queue

class Solution:

	def shortestPath(self, n: int, m: int, edge: List[List[int]]) -> List[int]:
		s = queue.Queue()
		adjList = {}
		indegree = []
		dist = [float('inf')] * n
		src = 0
		for i in range(n):
			adjList[i] = []
			indegree.append(0)
		for i in edge:
			u = i[0]
			v = i[1]
			w = i[2]
			adjList[u].append([v, w])
			indegree[v] += 1
		for i in range(n):
			if indegree[i] == 0:
				s.put(i)
		toposort = []
		while not s.empty():
			cur = s.get()
			toposort.append(cur)
			for i in adjList[cur]:
				v = i[0]
				indegree[v] -= 1
				if indegree[v] == 0:
					s.put(v)
		dist[src] = 0
		while len(toposort) > 0:
			cur = toposort.pop(0)
			cur_dist = dist[cur]
			for i in adjList[cur]:
				v = i[0]
				w = i[1]
				dist[v] = min(cur_dist + w, dist[v])
		for i in range(n):
			if dist[i] == float('inf'):
				dist[i] = -1
		return dist


from typing import List

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		graph = [[] for i in range(n)]
		for i in edges:
			graph[i[0]].append([i[1], i[2]])
		dist = [999999999] * n
		dist[0] = 0
		topolog = self.topo(n, graph)
		for i in topolog:
			for j in graph[i]:
				if dist[j[0]] > dist[i] + j[1]:
					dist[j[0]] = dist[i] + j[1]
		for i in range(len(dist)):
			if dist[i] == 999999999:
				dist[i] = -1
		return dist

	def topo(self, v, adj):
		ind = [0] * v
		for i in adj:
			for j in i:
				ind[j[0]] += 1
		(q, ans) = ([], [])
		for i in range(v):
			if ind[i] == 0:
				q.append(i)
		while len(q) > 0:
			u = q.pop(0)
			ans.append(u)
			for i in adj[u]:
				ind[i[0]] -= 1
				if ind[i[0]] == 0:
					q.append(i[0])
		return ans


from typing import List

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		distance = [100000] * n
		distance[0] = 0
		for i in range(n - 1):
			for edge in edges:
				u = edge[0]
				v = edge[1]
				w = edge[2]
				if distance[u] + w < distance[v]:
					distance[v] = distance[u] + w
		for i in range(len(distance)):
			if distance[i] == 100000:
				distance[i] = -1
		return distance


from collections import defaultdict
import math
from typing import List

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj_list = defaultdict(list)
		for i in range(len(edges)):
			node = edges[i][0]
			con = edges[i][1]
			weight = edges[i][2]
			adj_list[node].append([con, weight])

		def dfs(node):
			visited[node] = 1
			for (i, j) in adj_list[node]:
				if visited[i] == 0:
					dfs(i)
			ans.append(node)
		ans = []
		visited = [0 for i in range(n)]
		for k in range(n):
			if visited[k] == 0:
				dfs(k)
		dis = [math.inf for i in range(n)]
		dis[0] = 0
		while ans and ans[-1] != 0:
			ans.pop()
		while ans:
			node = ans.pop()
			for i in adj_list[node]:
				if i[1] + dis[node] < dis[i[0]]:
					dis[i[0]] = i[1] + dis[node]
		for i in range(n):
			if dis[i] == math.inf:
				dis[i] = -1
		return dis
		pass


from typing import List

class Solution:

	def topoSort(self, node, adj, vis, st):
		vis[node] = 1
		for ele in adj[node]:
			v = ele[0]
			if not vis[v]:
				st = self.topoSort(v, adj, vis, st)
		st.append(node)
		return st

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = [[] for _ in range(n)]
		for i in range(m):
			u = edges[i][0]
			v = edges[i][1]
			wt = edges[i][2]
			adj[u].append((v, wt))
		vis = [0] * n
		st = []
		for i in range(n):
			if not vis[i]:
				st = self.topoSort(i, adj, vis, st)
		dist = [float('inf') for _ in range(n)]
		dist[0] = 0
		while st:
			node = st.pop()
			for ele in adj[node]:
				v = ele[0]
				wt = ele[1]
				if dist[node] + wt < dist[v]:
					dist[v] = dist[node] + wt
		for i in range(n):
			if dist[i] == float('inf'):
				dist[i] = -1
		return dist


from typing import List

def topoSort(node, adj, vis, arr):
	if vis[node] == 1:
		return
	vis[node] = 1
	for nxt in adj[node]:
		(curr, dist) = nxt
		if vis[curr] == 0:
			topoSort(curr, adj, vis, arr)
	arr.append(node)

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		hmap = {}
		for i in range(n):
			hmap[i] = []
		for i in range(m):
			hmap[edges[i][0]].append((edges[i][1], edges[i][2]))
		(vis, stack) = ([0] * n, [])
		for i in range(n):
			if vis[i] != 1:
				topoSort(i, hmap, vis, stack)
		dist = [2 ** 32] * n
		dist[0] = 0
		while stack:
			node = stack.pop()
			for data in hmap[node]:
				(curr, dst) = data
				if dist[node] + dst < dist[curr]:
					dist[curr] = dist[node] + dst
		for i in range(n):
			if dist[i] == 2 ** 32:
				dist[i] = -1
		return dist


from collections import deque
from typing import List

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = {}
		for i in range(n):
			adj[i] = []
		for edge in edges:
			adj[edge[0]].append([edge[1], edge[2]])

		def dfs(node, adj, vis, stack):
			vis[node] = 1
			for adj_node in adj[node]:
				if vis[adj_node[0]] == -1:
					dfs(adj_node[0], adj, vis, stack)
			stack.appendleft(node)
		vis = [-1] * n
		stack = deque()
		for i in range(n):
			if vis[i] == -1:
				dfs(i, adj, vis, stack)
		dist = [float('inf')] * n
		dist[0] = 0
		while stack:
			node = stack.popleft()
			curr_distance = dist[node]
			for adj_node in adj[node]:
				new_wt = curr_distance + adj_node[1]
				if dist[adj_node[0]] > new_wt:
					dist[adj_node[0]] = new_wt
		for i in range(len(dist)):
			if dist[i] == float('inf'):
				dist[i] = -1
		return dist


from typing import List

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = [[] for _ in range(n)]
		for (node, adjNode, weight) in edges:
			adj[node].append([adjNode, weight])
		visited = [0] * n
		stack = []

		def dfs(node):
			visited[node] = 1
			for (adjNode, weight) in adj[node]:
				if visited[adjNode] == 0:
					dfs(adjNode)
			stack.append(node)
			return
		for node in range(n):
			if visited[node] == 0:
				dfs(node)
		distance = [float('inf')] * n
		distance[0] = 0
		while stack:
			node = stack.pop()
			for (adjNode, weight) in adj[node]:
				if distance[node] + weight < distance[adjNode]:
					distance[adjNode] = distance[node] + weight
		for (index, dist) in enumerate(distance):
			if dist == float('inf'):
				distance[index] = -1
		return distance


from typing import List

class Solution:

	def topoSort(self, node, adj, visited, st):
		visited[node] = True
		for v in adj[node]:
			if not visited[v[0]]:
				self.topoSort(v[0], adj, visited, st)
		st.append(node)

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = [[] for i in range(0, n)]
		for i in range(0, m):
			u = edges[i][0]
			v = edges[i][1]
			wt = edges[i][2]
			adj[u].append((v, wt))
		visited = [False for i in range(0, n)]
		st = []
		for i in range(0, n):
			if not visited[i]:
				self.topoSort(i, adj, visited, st)
		st.reverse()
		dist = [100000000 for i in range(0, n)]
		dist[0] = 0
		while len(st) > 0:
			node = st.pop(0)
			for u in adj[node]:
				v = u[0]
				wt = u[1]
				if dist[node] + wt < dist[v]:
					dist[v] = dist[node] + wt
		for i in range(0, n):
			if dist[i] == 100000000:
				dist[i] = -1
		return dist


from typing import List
from collections import defaultdict
from sys import maxsize

class Solution:

	def topo_sort(self, vertex, visited, adj, topo):
		visited[vertex] = 1
		for (nbr, wt) in adj[vertex]:
			if visited[nbr] == -1:
				self.topo_sort(nbr, visited, adj, topo)
		topo.append(vertex)

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = defaultdict(list)
		for (u, v, wt) in edges:
			adj[u].append((v, wt))
		visited = [-1] * n
		topo = []
		self.topo_sort(0, visited, adj, topo)
		dist = [maxsize] * n
		dist[0] = 0
		while topo:
			node = topo.pop()
			if dist[node] != maxsize:
				for (nbr, wt) in adj[node]:
					if dist[node] + wt < dist[nbr]:
						dist[nbr] = dist[node] + wt
		for i in range(n):
			if dist[i] == maxsize:
				dist[i] = -1
		return dist


from typing import List
from collections import defaultdict
import heapq

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = defaultdict(list)
		for (source, target, cost) in edges:
			adj[source].append((target, cost))
		output = [-1] * n
		heap = [(0, 0)]
		while heap:
			(time, node) = heapq.heappop(heap)
			if output[node] != -1:
				continue
			output[node] = time
			for (target, cost) in adj[node]:
				if output[target] == -1:
					heapq.heappush(heap, (time + cost, target))
		return output


from typing import List
from collections import defaultdict

class Solution:

	def topo(self, node, adj, vis, st):
		vis[node] = 1
		for it in adj[node]:
			if vis[it[0]] == 0:
				self.topo(it[0], adj, vis, st)
		st.append(node)

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = defaultdict(list)
		for (u, v, wt) in edges:
			adj[u].append([v, wt])
		vis = [0] * n
		st = []
		for i in range(n):
			if vis[i] == 0:
				self.topo(i, adj, vis, st)
		dist = [float('inf')] * n
		dist[0] = 0
		while st:
			node = st.pop()
			for (v, wt) in adj[node]:
				if dist[v] > wt + dist[node]:
					dist[v] = wt + dist[node]
		for i in range(n):
			if dist[i] == float('inf'):
				dist[i] = -1
		return dist


from typing import List
import heapq

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		d = {}
		for i in edges:
			if i[0] not in d:
				d[i[0]] = [[i[1], i[2]]]
			else:
				d[i[0]].append([i[1], i[2]])
		distance = [pow(10, 5) + 1 for _ in range(n)]
		q = [[0, 0]]
		distance[0] = 0
		heapq.heapify(q)
		while len(q) != 0:
			curE = heapq.heappop(q)
			try:
				for i in d[curE[1]]:
					nSum = curE[0] + i[1]
					if nSum < distance[i[0]]:
						distance[i[0]] = nSum
						heapq.heappush(q, [nSum, i[0]])
			except:
				continue
		for i in range(n):
			if distance[i] == pow(10, 5) + 1:
				distance[i] = -1
		return distance


import math
from typing import List

def dfs(node, adj, vis, st):
	vis[node] = 1
	for t in adj[node]:
		q = t[0]
		if vis[q] != 1:
			dfs(q, adj, vis, st)
	st.append(node)

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = [[] for i in range(n)]
		for i in range(m):
			u = edges[i][0]
			v = edges[i][1]
			wt = edges[i][2]
			adj[u].append((v, wt))
		vis = [0] * n
		st = []
		for i in range(n):
			if vis[i] != 1:
				dfs(i, adj, vis, st)
		dis = [math.inf] * n
		dis[0] = 0
		while st:
			node = st[-1]
			st.pop()
			for it in adj[node]:
				(v, wt) = (it[0], it[1])
				if dis[node] + wt < dis[v]:
					dis[v] = dis[node] + wt
		for i in range(len(dis)):
			if dis[i] == math.inf:
				dis[i] = -1
		return dis


from typing import List
from collections import *

class Solution:

	def dfs(self, node, adj, st, vis):
		vis[node] = 1
		for it in adj[node]:
			if not vis[it[0]]:
				Solution.dfs(self, it[0], adj, st, vis)
		st.append(node)

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = [[] for i in range(n)]
		for i in range(m):
			u = edges[i][0]
			v = edges[i][1]
			wt = edges[i][2]
			adj[u].append((v, wt))
		vis = [0] * n
		st = deque()
		for i in range(n):
			if not vis[i]:
				Solution.dfs(self, i, adj, st, vis)
		dis = [1000000000.0] * n
		dis[0] = 0
		flag = True
		while len(st) != 0:
			node = st.pop()
			if node == 0:
				flag = False
			for it in adj[node]:
				v = it[0]
				wt = it[1]
				dis[v] = min(dis[v], dis[node] + wt)
			if flag:
				dis[node] = -1
		return dis


from typing import List

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = []
		for i in range(0, n + 1):
			ax = []
			adj.append(ax)
		for i in range(0, len(edges)):
			a = edges[i][0]
			b = edges[i][1]
			c = edges[i][2]
			adj[a].append([b, c])
		visited = [False] * (n + 1)

		def topo(visited, stack1, i):
			visited[i] = True
			aa = adj[i]
			for k in range(0, len(aa)):
				if visited[aa[k][0]] == False:
					topo(visited, stack1, aa[k][0])
			stack1.append(i)
		stack1 = []
		for i in range(0, 1):
			if visited[i] == False:
				topo(visited, stack1, i)
		dis = [-1] * n
		dis[0] = 0
		for i in range(0, len(stack1)):
			if dis[stack1[-1]] != -1:
				aa1 = adj[stack1[-1]]
				ans1 = dis[stack1[-1]]
				stack1.pop()
				for j in range(0, len(aa1)):
					bb = aa1[j][0]
					bb1 = aa1[j][1]
					anstotal = ans1 + bb1
					if dis[bb] == -1:
						dis[bb] = anstotal
					elif anstotal < dis[bb]:
						dis[bb] = anstotal
		return dis


from typing import List
from collections import deque

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		(res, adj) = ([-1] * n, [[] for i in range(n)])
		for (a, b, d) in edges:
			adj[a].append((b, d))
		que = deque([(0, 0)])
		while que:
			(node, dis) = que.popleft()
			if res[node] == -1 or dis < res[node]:
				res[node] = dis
			for (adjNode, adjDis) in adj[node]:
				que.append((adjNode, dis + adjDis))
		return res


from typing import List
from collections import deque
import heapq

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = [[] for _ in range(n)]
		visited = [False for _ in range(n)]
		q = [[0, 0]]
		dis = [-1 for _ in range(n)]
		for (u, v, w) in edges:
			adj[u].append([w, v])
		while q:
			(d, e) = heapq.heappop(q)
			if visited[e]:
				continue
			visited[e] = True
			dis[e] = d
			for (w, v) in adj[e]:
				if not visited[v]:
					heapq.heappush(q, [d + w, v])
		return dis


from typing import List

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:

		def dfs(src, adj, stack, vis):
			vis[src] = 1
			for it in adj[src]:
				if it:
					if not vis[it[0]]:
						dfs(it[0], adj, stack, vis)
			stack.append(src)
		adj = [[] for i in range(n)]
		for i in range(m):
			adj[edges[i][0]].append([edges[i][1], edges[i][2]])
		vis = [0] * n
		stack = []
		for i in range(n):
			if vis[i] == 0:
				dfs(i, adj, stack, vis)
		dis = [float('inf') for _ in range(n)]
		dis[0] = 0
		while stack:
			node = stack.pop()
			for it in adj[node]:
				if it:
					v = it[0]
					wt = it[1]
					dis[v] = min(dis[v], dis[node] + wt)
		for i in range(len(dis)):
			if dis[i] == float('inf'):
				dis[i] = -1
		return dis


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

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adjList = defaultdict(list)
		for edge in edges:
			adjList[edge[0]].append([edge[1], edge[2]])
		visited = [False for i in range(n)]
		toposort = []
		for i in range(n):
			if not visited[i]:
				self.dfs(toposort, visited, adjList, i)
		dist = [sys.maxsize for i in range(n)]
		dist[0] = 0
		while toposort:
			node = toposort.pop()
			for edge in adjList[node]:
				nextNode = edge[0]
				wt = edge[1]
				if dist[node] + wt < dist[nextNode]:
					dist[nextNode] = dist[node] + wt
		for i in range(n):
			if dist[i] == sys.maxsize:
				dist[i] = -1
		return dist

	def dfs(self, toposort, visited, adjList, node):
		visited[node] = True
		for edge in adjList[node]:
			if visited[edge[0]] is False:
				self.dfs(toposort, visited, adjList, edge[0])
		toposort.append(node)


from typing import List
from collections import defaultdict, deque

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		path = defaultdict(list)
		for (u, v, w) in edges:
			path[u].append((v, w))
		dist = [float('inf')] * n
		q = deque()
		dist[0] = 0
		q.append((0, 0))
		while q:
			(node, wt) = q.popleft()
			for (i, weight) in path[node]:
				if dist[node] + weight < dist[i]:
					dist[i] = dist[node] + weight
					q.append((i, dist[i]))
		for i in range(n):
			if dist[i] == float('inf'):
				dist[i] = -1
		return dist


from typing import List

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:

		def dfs(adj, Node, vis, stack):
			visited[Node] = True
			for i in adj[Node]:
				if visited[i[0]] == False:
					dfs(adj, i[0], visited, stack)
			stack.append(Node)
		adj = [[] for i in range(n)]
		for ele in edges:
			adj[ele[0]].append([ele[1], ele[2]])
		visited = [False for i in range(n)]
		stack = []
		for i in range(n):
			if visited[i] == False:
				dfs(adj, i, visited, stack)
		dist = [999999999] * n
		dist[0] = 0
		while stack:
			temp = stack.pop()
			for i in adj[temp]:
				v = i[0]
				wt = i[1]
				if dist[temp] + wt < dist[v]:
					dist[v] = wt + dist[temp]
		for i in range(n):
			if dist[i] == 999999999:
				dist[i] = -1
		return dist


from typing import List
from collections import defaultdict

class Solution:

	def bfs(self, graph, v):
		indegree = [0] * v
		ans = []
		for i in range(v):
			for adj in graph[i]:
				indegree[adj[0]] += 1
		queue = []
		for i in range(v):
			if indegree[i] == 0:
				queue.append(i)
		while queue:
			temp = queue.pop(0)
			ans.append(temp)
			for adj in graph[temp]:
				indegree[adj[0]] -= 1
				if indegree[adj[0]] == 0:
					queue.append(adj[0])
		return ans

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		graph = defaultdict(list)
		for i in edges:
			graph[i[0]].append([i[1], i[2]])
		ans = self.bfs(graph, n)
		dist = [99999] * n
		dist[0] = 0
		while ans:
			x = ans.pop(0)
			for adj in graph[x]:
				v = adj[0]
				wt = adj[1]
				if dist[x] + wt < dist[v]:
					dist[v] = dist[x] + wt
		for i in range(n):
			if dist[i] == 99999:
				dist[i] = -1
		return dist
		pass


from typing import List
from collections import defaultdict as dq

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		graph = dq(list)
		ind = [0] * n
		visited = [0] * n
		dist = [0] * n
		for i in edges:
			graph[i[0]].append([i[1], i[2]])
			ind[i[1]] += 1
		q = [0]
		ptr = 0
		while ptr < len(q):
			for i in graph[q[ptr]]:
				ind[i[0]] -= 1
				if dist[i[0]] == 0:
					dist[i[0]] = dist[q[ptr]] + i[1]
				else:
					dist[i[0]] = min(dist[i[0]], dist[q[ptr]] + i[1])
				q.append(i[0])
			ptr += 1
		for i in range(1, n):
			if dist[i] == 0:
				dist[i] = -1
		return dist


from collections import defaultdict
from typing import List

class Solution:

	def topoSort(self, node, adj, vis, stack):
		vis[node] = 1
		for i in adj[node]:
			v = i[0]
			if not vis[v]:
				self.topoSort(v, adj, vis, stack)
		stack.append(node)

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = defaultdict(list)
		for (u, v, w) in edges:
			adj[u].append((v, w))
		stack = []
		vis = [0] * n
		for i in range(n):
			if not vis[i]:
				self.topoSort(i, adj, vis, stack)
		dist = [float('inf')] * n
		dist[0] = 0
		while stack:
			node = stack.pop()
			for i in adj[node]:
				(v, w) = i
				if dist[node] + w < dist[v]:
					dist[v] = dist[node] + w
		for i in range(n):
			if dist[i] == float('inf'):
				dist[i] = -1
		return dist


from typing import List
from heapq import *

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		dis = [float('inf')] * n
		dis[0] = 0
		adj_list = [[] for _ in range(n)]
		for i in edges:
			adj_list[i[0]].append((i[2], i[1]))
		queue = []
		heappush(queue, (0, 0))
		visited = [0] * n
		while queue:
			(d, j) = heappop(queue)
			visited[j] = 1
			for (d1, i) in adj_list[j]:
				if dis[i] > dis[j] + d1:
					dis[i] = dis[j] + d1
					heappush(queue, (dis[j] + d1, i))
		for i in range(n):
			if visited[i] == 0:
				dis[i] = -1
		return dis


from typing import List

def topoSort(node, vis, stack, adj):
	vis.add(node)
	for x in adj[node]:
		if x[0] not in vis:
			topoSort(x[0], vis, stack, adj)
	stack.append(node)

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = {}
		for i in range(n):
			adj[i] = []
		for edge in edges:
			adj[edge[0]].append([edge[1], edge[2]])
		vis = set()
		stack = []
		for i in range(n):
			if i not in vis:
				topoSort(i, vis, stack, adj)
		res = [float('inf') for i in range(n)]
		res[0] = 0
		while stack:
			popped = stack.pop()
			for x in adj[popped]:
				res[x[0]] = min(res[popped] + x[1], res[x[0]])
		for i in range(n):
			if res[i] == float('inf'):
				res[i] = -1
		return res


from typing import List
import heapq

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = [[] for i in range(n)]
		for (a, b, c) in edges:
			adj[a].append([b, c])
		li = [[0, 0]]
		dis = [float('inf')] * n
		dis[0] = 0
		while len(li) > 0:
			(c, node) = heapq.heappop(li)
			for (child, a) in adj[node]:
				if dis[node] + a < dis[child]:
					dis[child] = dis[node] + a
					heapq.heappush(li, [dis[child], child])
		for i in range(n):
			if dis[i] == float('inf'):
				dis[i] = -1
		return dis


from typing import List

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = [[] for i in range(n)]
		for (a, b, c) in edges:
			adj[a].append([b, c])
		tarr = []
		vis = [0] * n

		def dfstopo(node):
			for i in adj[node]:
				if vis[i[0]] == 0:
					vis[i[0]] = 1
					dfstopo(i[0])
			tarr.append(node)
		for i in range(n):
			if vis[i] == 0:
				vis[i] = 1
				dfstopo(i)
		dis = [float('inf')] * n
		dis[0] = 0
		j = n - 1
		while j >= 0:
			node = tarr[j]
			if dis[node] != float('inf'):
				for (a, b) in adj[node]:
					if dis[node] + b < dis[a]:
						dis[a] = dis[node] + b
			j -= 1
		for i in range(n):
			if dis[i] == float('inf'):
				dis[i] = -1
		return dis


from collections import defaultdict
from typing import List

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		graph = defaultdict(list)
		for (u, v, w) in edges:
			graph[u].append((v, w))
		dist_arr = [float('inf')] * n
		queue = [(0, 0)]
		dist_arr[0] = 0
		while queue:
			(node, dist) = queue.pop(0)
			for i in graph[node]:
				n = i[0]
				w = i[1]
				cur_dist = dist + w
				if dist_arr[n] > cur_dist:
					queue.append((n, cur_dist))
					dist_arr[n] = cur_dist
		dist_arr = [-1 if i == float('inf') else i for i in dist_arr]
		return dist_arr


import math
from typing import List
from collections import defaultdict

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = defaultdict(list)
		for (u, v, w) in edges:
			adj[u].append([v, w])
		dis = [math.inf] * n
		dis[0] = 0
		topo = []
		vis = [0] * n
		for i in range(n):
			if not vis[i]:
				self.dfs(adj, vis, topo, i)
		for i in range(n):
			node = topo.pop()
			distance = dis[node]
			for u in adj[node]:
				dis[u[0]] = min(dis[u[0]], u[1] + distance)
		for i in range(n):
			if dis[i] == math.inf:
				dis[i] = -1
		return dis

	def dfs(self, adj, vis, topo, s):
		vis[s] = 1
		for i in adj[s]:
			v = i[0]
			if not vis[v]:
				self.dfs(adj, vis, topo, v)
		topo.append(s)
		return


from typing import List
from collections import defaultdict
import math

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = defaultdict(list)
		visited = [0] * n
		for (u, v, w) in edges:
			adj[u].append([v, w])
		arr = []
		for i in range(n):
			if visited[i] == 0:
				self.dfs(visited, adj, arr, i)
		dist = [math.inf] * n
		dist[0] = 0
		while arr:
			s = arr.pop()
			for u in adj[s]:
				v = u[0]
				w = u[1]
				dist[v] = min(w + dist[s], dist[v])
		for i in range(n):
			if dist[i] == math.inf:
				dist[i] = -1
		return dist

	def dfs(self, visited, adj, arr, s):
		visited[s] = 1
		for u in adj[s]:
			if not visited[u[0]]:
				self.dfs(visited, adj, arr, u[0])
		arr.append(s)


from typing import List
from collections import defaultdict, deque

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		adj = defaultdict(list)
		dist = [float('inf') for _ in range(n)]
		for (u, v, d) in edges:
			adj[u].append((v, d))
		queue = deque()
		queue.append((0, 0))
		dist[0] = 0
		while queue:
			(u, d) = queue.popleft()
			for (v, nd) in adj[u]:
				if dist[v] > d + nd:
					dist[v] = d + nd
					queue.append((v, nd + d))
		for i in range(n):
			if dist[i] == float('inf'):
				dist[i] = -1
		return dist


from collections import deque
from typing import List

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		ans = [99999] * n
		grph = [[] for i in range(n)]
		dic = {}
		for edge in edges:
			x = edge[0]
			y = edge[1]
			dist = edge[2]
			grph[x].append(y)
			dic[x, y] = dist
		src = 0
		q = deque()
		ans[src] = 0
		q.append([src, 0])
		while q:
			(p, dist) = q.pop()
			for el in grph[p]:
				if ans[el] > dist + dic[p, el]:
					ans[el] = dist + dic[p, el]
					q.appendleft([el, dist + dic[p, el]])
		for i in range(n):
			if ans[i] == 99999:
				ans[i] = -1
		return ans


from typing import List

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		q = [0]
		dist = []
		for i in range(n):
			dist.append(999999)
		adj = []
		for i in range(n):
			adj.append([])
		for i in range(m):
			adj[edges[i][0]].append([edges[i][1], edges[i][2]])
		dist[0] = 0
		while len(q) != 0:
			node = q[0]
			q.pop(0)
			for i in adj[node]:
				q.append(i[0])
				dist[i[0]] = min(dist[i[0]], dist[node] + i[1])
		for i in range(len(dist)):
			if dist[i] == 999999:
				dist[i] = -1
		return dist


from typing import List
from queue import PriorityQueue

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		graph = [[] for _ in range(n)]
		for (u, v, w) in edges:
			graph[u].append((v, w))
		distance = [float('inf')] * n
		distance[0] = 0
		pq = PriorityQueue()
		pq.put((0, 0))
		visited = set()
		while not pq.empty():
			(dist, u) = pq.get()
			if u in visited:
				continue
			visited.add(u)
			for (v, w) in graph[u]:
				if distance[u] + w <= distance[v]:
					distance[v] = distance[u] + w
					pq.put((distance[v], v))
		for i in range(n):
			if distance[i] == float('inf'):
				distance[i] = -1
		return distance


from typing import List
from collections import deque

class Solution:

	def shortestPath(self, n: int, m: int, edges: List[List[int]]) -> List[int]:
		q = deque()
		adjList = [[] for _ in range(n)]
		indegrees = [0] * n
		dis = [float('inf')] * n
		for edge in edges:
			(i, j, k) = (edge[0], edge[1], edge[2])
			adjList[i].append([j, k])
			indegrees[j] += 1
		for (idx, k) in enumerate(indegrees):
			if k == 0:
				q.append(idx)
		topOrder = []
		while q:
			curr = q.popleft()
			topOrder.append(curr)
			for j in adjList[curr]:
				(v, weight) = (j[0], j[1])
				indegrees[v] -= 1
				if indegrees[v] == 0:
					q.append(v)
		dis[topOrder[0]] = 0
		for j in topOrder:
			for edge in adjList[j]:
				(k, weight) = (edge[0], edge[1])
				dis[k] = min(dis[k], weight + dis[j])
		for (idx, i) in enumerate(dis):
			if i == float('inf'):
				dis[idx] = -1
		return dis