Given a Weighted Directed Acyclic Graph (DAG) and a source vertex s in it, find the longest distances from s to all other vertices in the given graph.
Example 1:
Input:
N=3
M=2
SRC=0
edges[]={{0,2,1},{0,1,1}}
Output:
distance[]={0,1,1}
Explanation:
the shortest distance of vertex 1 from 0 is 1 and that of two is also 1.
 
Example 2:
Input:
N=6
M=10
SRC=1
edges[]={{0,1,5},{0,2,3},{1,3,6},{1,2,2},{2,4,4},{2,5,2},{2,3,7},{3,5,1},{3,4,-1},{4,5,-2}}
Output:
distance[]={INF,0,2,9,8,10}
Explanation:
The vertex zero is not reachable from vertex 1 so its distance is INF, for 2 it is 2, for 3 it is 9, the same goes for 4 and 5.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function maximumDistance() which takes the edge list edges[] where edges[0] , edges[1] and edges[2] represent u,v and weight, its size M and the number of nodes N as input parameters and returns the distance array in the distance array instead of passing INF you need to have INT_MIN driver will automatically update it to INF.
 
Expected Time Complexity: O(V+E)
Expected Auxiliary Space: O(V)
 
Constraints:
1 <= N <= 10^{3}
1<=M<=N*(N-1)/2
0<=edges[i][0],edges[i][1]
-100<=edges[i][2]<=100.

Source: geeksforgeeks | Difficulty: MEDIUM_HARD

Starter code: from typing import List





from typing import List





class Solution:

    def maximumDistance(self, v : int, e : int, src : int, edges : List[List[int]]) -> List[int]:

        # code here

        



Solutions:
from typing import List
import sys
from typing import List
from collections import defaultdict as dict, deque as dq

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		n = v
		adj = dict(list)
		dist = [-float('inf') for i in range(v)]
		visited = set()
		q = dq([(src, 0)])
		topo = []

		def postDfs(node):
			for (neib, w) in adj[node]:
				if neib not in visited:
					postDfs(neib)
			visited.add(node)
			topo.append(node)
		for edge in edges:
			(u, v, w) = (edge[0], edge[1], edge[2])
			adj[u].append((v, w))
		for i in range(n):
			if i not in visited:
				postDfs(i)
		dist[src] = 0
		while topo:
			node = topo.pop(-1)
			nodeDist = dist[node]
			for (neib, w) in adj[node]:
				if dist[neib] < nodeDist + w:
					dist[neib] = nodeDist + w
		for (i, d) in enumerate(dist):
			if d == float('-inf'):
				dist[i] = 'INF'
		return dist


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

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		hmap = {}
		for (i, j, k) in edges:
			if i not in hmap:
				hmap[i] = [(j, k)]
			else:
				hmap[i].append((j, k))
		dist = [-1000000000.0] * v
		dist[src] = 0
		que = deque([src])
		while que:
			node = que.popleft()
			if node in hmap:
				for ngbr in hmap[node]:
					next_node = ngbr[0]
					next_dist = ngbr[1]
					if dist[node] + next_dist > dist[next_node]:
						dist[next_node] = next_dist + dist[node]
						que.append(next_node)
		for i in range(v):
			if dist[i] == -1000000000.0:
				dist[i] = 'INF'
		return dist


from typing import List
from typing import List

class Solution:

	def dfs(self, node, graph, dis, curr):
		dis[node] = max(dis[node], curr)
		for i in graph[node]:
			(u, wt) = (i[0], i[1])
			if dis[u] == -float('inf') or dis[u] < curr + wt:
				self.dfs(u, graph, dis, curr + wt)

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		dis = [-float('inf') for i in range(v)]
		graph = {}
		for i in range(v):
			graph[i] = []
		for i in edges:
			(a, b, wt) = (i[0], i[1], i[2])
			graph[a].append([b, wt])
		self.dfs(src, graph, dis, 0)
		for i in range(v):
			if dis[i] == -float('inf'):
				dis[i] = 'INF'
		return dis


from typing import List
from collections import deque

class Solution:

	def maximumDistance(self, n: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		graph = {u: set() for u in range(n)}
		for (u, v, d) in edges:
			graph[u].add((v, d))
		dist = [float('-inf')] * n
		Q = deque()
		Q.append([src, 0])
		while Q:
			(u, d) = Q.popleft()
			if d < dist[u]:
				continue
			dist[u] = d
			for (v, dv) in graph[u]:
				Q.append([v, d + dv])
		for u in range(n):
			if dist[u] == float('-inf'):
				dist[u] = 'INF'
		return dist


from typing import List
from typing import List

class Solution:

	def topoSort(self, node, vis, stk, g):
		vis.add(node)
		for child in g[node]:
			if child[0] not in vis:
				self.topoSort(child[0], vis, stk, g)
		stk.append(node)

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		g = [[] for i in range(v)]
		for i in range(e):
			g[edges[i][0]].append((edges[i][1], edges[i][2]))
		vis = set()
		stk = []
		for node in range(v):
			if node not in vis:
				self.topoSort(node, vis, stk, g)
		dist = [-float('inf')] * v
		dist[src] = 0
		while stk:
			node = stk.pop()
			if dist[node] != -float('inf'):
				for child in g[node]:
					if dist[node] + child[1] > dist[child[0]]:
						dist[child[0]] = dist[node] + child[1]
		for i in range(v):
			if dist[i] == -float('inf'):
				dist[i] = 'INF'
		return dist


from typing import List
from typing import List
from collections import defaultdict
import math

class Solution:

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

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


from typing import List
import heapq

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		adj = {v: [] for v in range(v)}
		for (s, d, w) in edges:
			adj[s].append((d, -w))
		minHeap = [(0, src)]
		destinations = [float('inf') for _ in range(v)]
		destinations[src] = 0
		while minHeap:
			(cost, curNode) = heapq.heappop(minHeap)
			for (nei, neiCost) in adj[curNode]:
				if cost + neiCost <= destinations[nei]:
					destinations[nei] = cost + neiCost
					heapq.heappush(minHeap, (cost + neiCost, nei))
		for i in range(v):
			if destinations[i] != float('inf'):
				destinations[i] = -destinations[i]
			else:
				destinations[i] = 'INF'
		return destinations


from typing import List
from typing import List

class Solution:

	def maximumDistance(self, ve: int, e: int, src: int, all_edges: List[List[int]]) -> List[int]:

		def topo_dfs(node, st, adj, vis):
			vis[node] = 1
			for i in adj[node]:
				u = i[0]
				if vis[u] == 0:
					topo_dfs(u, st, adj, vis)
			st.append(node)
		adj = {}
		vis = []
		st = []
		dis = []
		n = len(edges)
		for i in range(ve):
			adj[i] = []
			vis.append(0)
			dis.append(float('-inf'))
		for i in all_edges:
			u = i[0]
			v = i[1]
			w = i[2]
			adj[u].append([v, w])
		for i in range(ve):
			if vis[i] == 0:
				topo_dfs(i, st, adj, vis)
		dis[src] = 0
		while len(st) != 0:
			t = st.pop()
			d = dis[t]
			for i in adj[t]:
				v = i[0]
				w = i[1]
				if d + w > dis[v]:
					dis[v] = d + w
		for i in range(len(dis)):
			if dis[i] == float('-inf'):
				dis[i] = 'INF'
		return dis


from typing import List
import heapq

class Solution:

	def maximumDistance(self, v: int, e2: int, src: int, edges: List[List[int]]) -> List[int]:
		q = list()
		graph = dict()
		for e in edges:
			graph[e[0]] = [[e[2], e[1]]] + graph.get(e[0], [])
		distance = [-1] * v
		distance[src] = 0
		for (weight, dest) in graph.get(src, []):
			distance[dest] = distance[src] + weight
			q.append(dest)
		while q:
			cur = q.pop(0)
			for (weight, dest) in graph.get(cur, []):
				if distance[dest] < distance[cur] + weight:
					distance[dest] = distance[cur] + weight
					q.append(dest)
		for i in range(v):
			if distance[i] == -1:
				distance[i] = 'INF'
		return distance


from typing import List
from typing import List
import sys
INF = sys.maxsize

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		adj = []
		for i in range(0, v):
			adj.append([])
		for edge in edges:
			(dst, source, w) = edge
			adj[source].append((dst, w))
		dp = {}
		dp[src] = 0
		for i in range(0, v):
			if len(adj[i]) == 0 and i != src:
				dp[i] = -INF

		def dfs(node):
			if node in dp:
				return dp[node]
			maxDist = -INF
			for (neigh, w) in adj[node]:
				dist = dfs(neigh)
				if dist == -INF:
					continue
				dist += w
				maxDist = max(maxDist, dist)
			dp[node] = maxDist
			return maxDist
		ans = []
		for i in range(0, v):
			ans.append(dfs(i) if dfs(i) != -INF else 'INF')
		return ans


from typing import List
from typing import List
from collections import *

class Solution:

	def toposort(self, s, node, graph, vis):
		vis[node] = True
		for nbr in graph[node]:
			if not vis[nbr[0]]:
				self.toposort(s, nbr[0], graph, vis)
		s.append(node)

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		s = []
		graph = defaultdict(list)
		vis = [False] * v
		for i in edges:
			graph[i[0]].append([i[1], i[2]])
		for i in range(v):
			if not vis[i]:
				self.toposort(s, i, graph, vis)
		dist = [-1000000000.0] * v
		dist[src] = 0
		while s:
			node = s.pop()
			if dist[node] != -1000000000.0:
				for nbr in graph[node]:
					u = nbr[0]
					w = nbr[1]
					if dist[u] < dist[node] + w:
						dist[u] = dist[node] + w
		for i in range(len(dist)):
			if dist[i] == -1000000000.0:
				dist[i] = 'INF'
		return dist


from typing import List
from typing import List

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		dis = [float('-inf')] * v
		adj = dict()
		indeg = [0] * v
		dis[src] = 0
		for i in edges:
			if i[0] not in adj:
				adj[i[0]] = [[i[1], i[2]]]
			else:
				adj[i[0]].append([i[1], i[2]])
			indeg[i[1]] += 1
		q = []
		for i in range(v):
			if indeg[i] == 0:
				q.append(i)
		topo = []
		while len(q) != 0:
			x = q.pop(0)
			topo.append(x)
			if x in adj:
				for (a, b) in adj[x]:
					indeg[a] -= 1
					if indeg[a] == 0:
						q.append(a)
		for i in topo:
			if i in adj:
				for j in adj[i]:
					if dis[i] == float('-inf'):
						continue
					if dis[j[0]] < dis[i] + j[1]:
						dis[j[0]] = dis[i] + j[1]
		res = dis.copy()
		for i in range(len(dis)):
			if dis[i] == float('-inf'):
				res[i] = 'INF'
		return res


from typing import List
from typing import List

class Solution:

	def dfs(self, u, adj, visited, stack):
		visited[u] = True
		for (v, w) in adj[u]:
			if not visited[v]:
				self.dfs(v, adj, visited, stack)
		stack.append(u)

	def maximumDistance(self, V: int, E: int, src: int, edges: List[List[int]]) -> List[int]:
		adj = {i: [] for i in range(V)}
		for (u, v, w) in edges:
			adj[u].append([v, w])
		visited = [False] * V
		stack = []
		self.dfs(src, adj, visited, stack)
		NEG_INF = -(1 << 63)
		dist = [NEG_INF] * V
		dist[src] = 0
		while stack:
			u = stack.pop()
			for (v, w) in adj[u]:
				if dist[u] + w > dist[v]:
					dist[v] = dist[u] + w
		for u in range(V):
			if dist[u] == NEG_INF:
				dist[u] = 'INF'
		return dist


from typing import List
from math import inf
from heapq import heappush as push, heappop as pop

class Solution:

	def maximumDistance(self, n: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		x = [[] for i in range(n)]
		dp = [None for i in range(n)]
		dp[src] = 0
		for (a, b, c) in edges:
			x[b].append((a, c))

		def f(i):
			if i == src:
				return 0
			if dp[i] != None:
				return dp[i]
			ans = -inf
			for (j, k) in x[i]:
				ans = max(ans, k + f(j))
			dp[i] = ans
			return ans
		for i in range(n):
			f(i)
		return ['INF' if i == -inf else i for i in dp]


from typing import List
import math
from heapq import heappop, heappush

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		adj = [[] for i in range(v)]
		for (a, b, c) in edges:
			adj[a].append([b, c])
		dist = [-math.inf] * v
		dist[src] = 0
		pq = []
		heappush(pq, (0, src))
		while pq:
			(dis, nod) = heappop(pq)
			for (x, y) in adj[nod]:
				if dist[x] < y + dis:
					heappush(pq, (y + dis, x))
					dist[x] = y + dis
		for i in range(v):
			if dist[i] == -math.inf:
				dist[i] = 'INF'
		return dist


from collections import deque
from math import inf

class Solution:

	def maximumDistance(self, n, m, src, edges):
		(in_deg_arr, adj_lst) = ([0 for i in range(n)], [[] for i in range(n)])
		(q, res) = (deque(), [-inf for i in range(n)])
		res[src] = 0
		for (start, end, weight) in edges:
			in_deg_arr[end] += 1
			adj_lst[start].append([end, weight])
		for i in range(n):
			if in_deg_arr[i] == 0:
				q.append(i)
		while q:
			idx = q.popleft()
			for (next_idx, wt) in adj_lst[idx]:
				in_deg_arr[next_idx] -= 1
				res[next_idx] = max(res[next_idx], res[idx] + wt)
				if in_deg_arr[next_idx] == 0:
					q.append(next_idx)
		for i in range(n):
			if res[i] == -inf:
				res[i] = 'INF'
		return res


from typing import List
import math

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		adj = [[] for i in range(v)]
		for (a, b, c) in edges:
			adj[a].append([b, c])
		distance = [-math.inf for i in range(v)]
		distance[src] = 0
		q = []
		q.append(src)
		while q:
			node = q.pop()
			for (val, wt) in adj[node]:
				if distance[val] < distance[node] + wt:
					distance[val] = distance[node] + wt
					q.append(val)
		for i in range(v):
			if distance[i] == -math.inf:
				distance[i] = 'INF'
		return distance


from typing import List
import sys
from heapq import heappop, heappush
import math

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		adj = [[] for i in range(v)]
		for (a, b, c) in edges:
			adj[a].append([b, c])
		distance = [-math.inf for i in range(v)]
		distance[src] = 0
		q = []
		heappush(q, [0, src])
		while q:
			(d, node) = heappop(q)
			d = -1 * d
			for (val, wt) in adj[node]:
				if distance[val] < d + wt:
					distance[val] = d + wt
					heappush(q, [-distance[val], val])
		for i in range(v):
			if distance[i] == -math.inf:
				distance[i] = 'INF'
		return distance


from typing import List
import sys
import math
from heapq import heappop, heappush

class Solution:

	def maximumDistance(self, V, e, src, edges):
		dis = [-math.inf for i in range(V)]
		adj = [[] for i in range(V)]
		for (u, v, w) in edges:
			adj[u].append([v, w])
		vis = [0 for i in range(V)]
		dis[src] = 0
		q = []
		heappush(q, [0, src])
		while q:
			(d, node) = heappop(q)
			d = -1 * d
			for (ad, w) in adj[node]:
				if dis[ad] < w + d:
					dis[ad] = w + d
					heappush(q, [-dis[ad], ad])
		for i in range(V):
			if dis[i] == -math.inf:
				dis[i] = 'INF'
		return dis


from typing import List
from typing import List
import sys

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, adj: List[List[int]]) -> List[int]:

		def topological(adj, v, visit, stack):
			visit[v] = True
			for i in adj[v]:
				if visit[i[0]] == False:
					topological(adj, i[0], visit, stack)
			stack.append(v)
		mat = [[] for i in range(v)]
		for i in range(e):
			mat[adj[i][0]].append([adj[i][1], adj[i][2]])
		stack = []
		visit = [False] * v
		for i in range(v):
			if visit[i] == False:
				topological(mat, i, visit, stack)
		dist = [-sys.maxsize for i in range(v)]
		dist[src] = 0
		while stack:
			u = stack[-1]
			stack.pop()
			if dist[u] != -sys.maxsize:
				for i in mat[u]:
					if dist[i[0]] < dist[u] + i[1]:
						dist[i[0]] = dist[u] + i[1]
		for i in range(v):
			if dist[i] == -sys.maxsize:
				dist[i] = 'INF'
		return dist


from typing import List
from typing import List
import heapq as h

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		adj = [None] * v
		for (u, V, c) in edges:
			if adj[u]:
				adj[u].append([V, c])
			else:
				adj[u] = [[V, c]]
		for i in range(v):
			if not adj[i]:
				adj[i] = []
		he = []
		h.heapify(he)
		dist = [-float('inf') for i in range(v)]
		dist[src] = 0
		h.heappush(he, (0, src))
		while he:
			(dist_u, u) = h.heappop(he)
			v = adj[u]
			for (var, cost) in v:
				if dist[var] < dist_u + cost:
					dist[var] = dist_u + cost
					h.heappush(he, (dist[var], var))
		op = []
		for i in dist:
			if i == -float('inf'):
				op.append('INF')
			else:
				op.append(i)
		return op


from typing import List
from typing import List

class Solution:

	def create(self, edges, m, V):
		graph = [[] for i in range(V)]
		for i in range(m):
			graph[edges[i][0]].append([edges[i][1], edges[i][2]])
		return graph

	def topo(self, i, graph):
		vis[i] = 1
		for j in graph[i]:
			if vis[j[0]] == 0:
				self.topo(j[0], graph)
		stack.append(i)

	def maximumDistance(self, V: int, m: int, src: int, edges: List[List[int]]) -> List[int]:
		graph = self.create(edges, m, V)
		dist = [float('-Inf') for i in range(V)]
		dist[src] = 0
		global vis
		global stack
		vis = [0 for i in range(V)]
		stack = []
		for i in range(V):
			if vis[i] == 0:
				self.topo(i, graph)
		while stack:
			n = stack.pop()
			for j in graph[n]:
				if dist[j[0]] < dist[n] + j[1]:
					dist[j[0]] = dist[n] + j[1]
		for i in range(V):
			if dist[i] == float('-Inf'):
				dist[i] = 'INF'
		return dist


from typing import List
from typing import List
import collections

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		adj_list = collections.defaultdict(list)
		for (V, U, W) in edges:
			adj_list[V].append((U, W))

		def dfs(node):
			visited[node] = True
			for (neighbor, weight) in adj_list[node]:
				if not visited[neighbor]:
					dfs(neighbor)
			stack.append(node)
		stack = []
		visited = [False] * v
		for i in range(v):
			if not visited[i]:
				dfs(i)
		dist = [float('-inf')] * v
		dist[src] = 0
		stack.append(src)
		while stack:
			node = stack.pop()
			for (neighbor, weight) in adj_list[node]:
				if dist[node] + weight > dist[neighbor]:
					dist[neighbor] = dist[node] + weight
		result = []
		for d in dist:
			if d == float('-inf'):
				result.append('INF')
			else:
				result.append(d)
		return result


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

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		n = v
		graph = defaultdict(list)
		self.res = []
		visited = [False] * n
		for (u, v, w) in edges:
			graph[u].append((v, w))

		def topo(node, visited):
			visited[node] = True
			for (v, w) in graph[node]:
				if visited[v] == False:
					topo(v, visited)
			self.res.append(node)
		for i in range(n):
			if visited[i] == False:
				topo(i, visited)
		dist = [float('-inf')] * n
		dist[src] = 0
		for i in range(n - 1, -1, -1):
			if dist[self.res[i]] != float('-inf'):
				for j in graph[self.res[i]]:
					v = j[0]
					w = j[1]
					if dist[self.res[i]] + w > dist[v]:
						dist[v] = dist[self.res[i]] + w
		for i in range(n):
			if dist[i] == float('-inf'):
				dist[i] = 'INF'
		return dist


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

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		adj = defaultdict(list)
		for (s, d, w) in edges:
			adj[s].append((d, w))
		dist = [-float('inf')] * v

		def dfs(node, d):
			dist[node] = max(d, dist[node])
			for (neigh, w) in adj[node]:
				if d + w > dist[neigh]:
					dfs(neigh, d + w)
		dfs(src, 0)
		for i in range(v):
			if dist[i] == -float('inf'):
				dist[i] = 'INF'
		return dist

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		v = int(input())
		e = int(input())
		src = int(input())
		edges = IntMatrix().Input(e, e)
		obj = Solution()
		res = obj.maximumDistance(v, e, src, edges)
		IntArray().Print(res)


from typing import List
from typing import List

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		adj = []
		for a in range(v):
			adj.append([])
		for (sr, ds, w) in edges:
			adj[sr].append([ds, w])
		order = []

		def topo(s):
			visited[s] = 1
			for y in range(len(adj[s])):
				if visited[adj[s][y][0]] == 0:
					topo(adj[s][y][0])
			order.append(s)
		visited = [0] * v
		for x in range(v):
			if visited[x] == 0:
				topo(x)
		d = [float('-inf')] * v
		d[src] = 0
		for i in range(len(order) - 1, -1, -1):
			if d[order[i]] != float('-inf'):
				u = order[i]
				for j in range(len(adj[u])):
					v = adj[u][j][0]
					w = adj[u][j][1]
					if d[u] + w > d[v]:
						d[v] = w + d[u]
		for g in range(len(d)):
			if d[g] == float('-inf'):
				d[g] = 'INF'
		return d
		dfs(src)
		for j in range(len(d)):
			if d[j] == -1:
				d[j] = 'INF'
		return d

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		v = int(input())
		e = int(input())
		src = int(input())
		edges = IntMatrix().Input(e, e)
		obj = Solution()
		res = obj.maximumDistance(v, e, src, edges)
		IntArray().Print(res)


from typing import List
import sys
from typing import List

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		graph = [[] for i in range(v)]
		for i in range(e):
			graph[edges[i][0]].append((edges[i][1], edges[i][2]))
		ans = ['INF' for i in range(v)]
		ans[src] = 0
		stack = []
		visited = [0 for i in range(v)]

		def dfs(node):
			visited[node] = 1
			for i in graph[node]:
				if not visited[i[0]]:
					dfs(i[0])
			stack.append(node)
		for i in range(v):
			if not visited[i]:
				dfs(i)
		stack.reverse()
		for start in stack:
			if ans[start] != 'INF':
				for i in graph[start]:
					if ans[i[0]] != 'INF':
						ans[i[0]] = max(ans[i[0]], ans[start] + i[1])
					else:
						ans[i[0]] = ans[start] + i[1]
		return ans

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		v = int(input())
		e = int(input())
		src = int(input())
		edges = IntMatrix().Input(e, e)
		obj = Solution()
		res = obj.maximumDistance(v, e, src, edges)
		IntArray().Print(res)


from typing import List
from typing import List
import sys

class Solution:

	def maximumDistance(self, v, e, src, edges):
		adjl = [[] for j in range(v)]
		indegree = [0 for i in range(v)]
		for e in edges:
			adjl[e[0]].append([e[1], e[2]])
			indegree[e[1]] += 1
		weight = [-1000000 for i in range(v)]
		weight[src] = 0
		q = []
		for i in range(v):
			if indegree[i] == 0:
				q.append(i)
		flag = 0
		while q:
			p = q.pop(0)
			if int(p) == src:
				flag = 1
			if flag == 0:
				for j in adjl[p]:
					indegree[j[0]] -= 1
					if indegree[j[0]] == 0:
						q.append(j[0])
			if flag == 1:
				for j in adjl[p]:
					indegree[j[0]] -= 1
					weight[j[0]] = max(weight[j[0]], weight[p] + j[1])
					if indegree[j[0]] == 0:
						q.append(j[0])
		for i in range(len(weight)):
			if -1000000 <= weight[i] <= -1000:
				weight[i] = 'INF'
			else:
				weight[i] = str(weight[i])
		return weight

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()

class IntArray:

	def __init__(self) -> None:
		pass

	def Input(self, n):
		arr = [int(i) for i in input().strip().split()]
		return arr

	def Print(self, arr):
		for i in arr:
			print(i, end=' ')
		print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		v = int(input())
		e = int(input())
		src = int(input())
		edges = IntMatrix().Input(e, e)
		obj = Solution()
		res = obj.maximumDistance(v, e, src, edges)
		IntArray().Print(res)


from typing import List
from typing import List
import math

class Solution:

	def __init__(self):
		self.vs = []
		self.s = []
		self.g = []

	def add(self, u, v, w):
		self.g[u].append((v, w))

	def top(self, x, adj):
		self.vs[x] = True
		for i in adj[x]:
			if self.vs[i[0]] == False:
				self.top(i[0], adj)
		self.s.append(x)

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		for i in range(v):
			self.g.append([])
		for i in edges:
			self.add(i[0], i[1], i[2])
		self.vs = [False] * v
		for i in range(v):
			if self.vs[i] == False:
				self.top(i, self.g)
		self.s.reverse()
		dis = [float('-inf')] * v
		dis[src] = 0
		while self.s:
			x = self.s.pop(0)
			for i in self.g[x]:
				if dis[i[0]] < dis[x] + i[1]:
					dis[i[0]] = dis[x] + i[1]
		for i in range(len(dis)):
			if dis[i] == float('-inf'):
				dis[i] = 'INF'
		return dis


from typing import List
from typing import List

class Solution:

	def maximumDistance(self, V: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		adj = [[] for _ in range(V)]
		visit = [False for _ in range(V)]
		for (u, v, wt) in edges:
			adj[u].append((v, wt))
		order = []

		def topo(node):
			visit[node] = True
			for (neigh, _) in adj[node]:
				if not visit[neigh]:
					topo(neigh)
			order.append(node)
		topo(src)
		import math
		distance = [-math.inf for _ in range(V)]
		distance[src] = 0
		while order:
			node = order.pop()
			for (neigh, wt) in adj[node]:
				if distance[neigh] < distance[node] + wt:
					distance[neigh] = distance[node] + wt
		for i in range(len(distance)):
			if distance[i] == -math.inf:
				distance[i] = 'INF'
		return distance


from typing import List
import sys

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		stack = []
		adj = [[] for i in range(v)]
		for (i, j, wt) in edges:
			adj[i].append([j, wt])
		visited = [0] * v
		dist = [-101] * v
		dist[src] = 0

		def toposort(i):
			visited[i] = 1
			for j in adj[i]:
				if not visited[j[0]]:
					toposort(j[0])
			stack.append(i)
		for i in range(v):
			if not visited[i]:
				toposort(i)
		while stack:
			node = stack.pop()
			if dist[node] != -101:
				for i in adj[node]:
					if dist[i[0]] < dist[node] + i[1]:
						dist[i[0]] = dist[node] + i[1]
		for i in range(len(dist)):
			if dist[i] == -101:
				dist[i] = 'INF'
		return dist


from typing import List

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		ans = [float('-inf')] * v
		graph = {i: [] for i in range(v)}
		for (p, q, w) in edges:
			graph[p].append([q, w])

		def rec(i, d):
			if ans[i] >= d:
				return
			ans[i] = d
			for (j, w) in graph[i]:
				rec(j, d + w)
		rec(src, 0)
		return [num if num > float('-inf') else 'INF' for num in ans]


from typing import List
from typing import List

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:

		def bfs(vertex):
			dis[vertex] = 0
			q = [vertex]
			while q:
				u = q.pop(0)
				for (v, w) in adj[u]:
					if dis[v] < dis[u] + w:
						dis[v] = dis[u] + w
						q.append(v)
		adj = [[] for i in range(v)]
		for i in edges:
			adj[i[0]].append((i[1], i[2]))
		dis = [float('-inf') for i in range(v)]
		bfs(src)
		for i in range(v):
			if dis[i] == float('-inf'):
				dis[i] = 'INF'
		return dis


from typing import List
from collections import deque
import sys

class Solution:

	def maximumDistance(self, V: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		indegree = [0] * V
		adj = [[] for i in range(V)]
		for (u, v, w) in edges:
			indegree[v] += 1
			adj[u].append([v, w])
		queue = deque()
		for i in range(V):
			if indegree[i] == 0:
				queue.append(i)
		topology = []
		while queue:
			node = queue.popleft()
			topology.append(node)
			for (i, w) in adj[node]:
				indegree[i] -= 1
				if indegree[i] == 0:
					queue.append(i)
		dist = [-101] * V
		dist[src] = 0
		for u in topology:
			if dist[u] != -101:
				for (v, w) in adj[u]:
					if dist[v] < dist[u] + w:
						dist[v] = dist[u] + w
		for i in range(V):
			if dist[i] <= -101:
				dist[i] = 'INF'
		return dist


from typing import List
from typing import List
import math
from collections import deque

class Solution:

	def maximumDistance(self, v: int, e: int, src: int, edges: List[List[int]]) -> List[int]:
		inf = 'INF'
		temp = float('-inf')
		dist = [temp] * v
		dist[src] = 0
		matrix = []
		for i in range(v):
			x = []
			for j in range(v):
				x.append(temp)
			matrix.append(x)
		for (u, v, w) in edges:
			matrix[u][v] = w
		q = deque()
		q.append(src)
		while q:
			row = q.popleft()
			for col in range(len(matrix[0])):
				if dist[row] + matrix[row][col] > dist[col]:
					dist[col] = dist[row] + matrix[row][col]
					q.append(col)
		for i in range(len(dist)):
			if dist[i] == temp:
				dist[i] = inf
		return dist