There are n houses and p water pipes in Geek Colony. Every house has at most one pipe going into it and at most one pipe going out of it. Geek needs to install pairs of tanks and taps in the colony according to the following guidelines.  
1. Every house with one outgoing pipe but no incoming pipe gets a tank on its roof.
2. Every house with only one incoming and no outgoing pipe gets a tap.
The Geek council has proposed a network of pipes where connections are denoted by three input values: ai, bi, di denoting the pipe of diameter di from house ai to house bi.
Find a more efficient way for the construction of this network of pipes. Minimize the diameter of pipes wherever possible.
Note: The generated output will have the following format. The first line will contain t, denoting the total number of pairs of tanks and taps installed. The next t lines contain three integers each: house number of tank, house number of tap, and the minimum diameter of pipe between them.
Example 1:
Input:
n = 9, p = 6
a[] = {7,5,4,2,9,3}
b[] = {4,9,6,8,7,1}
d[] = {98,72,10,22,17,66} 
Output: 
3
2 8 22
3 1 66
5 6 10
Explanation:
Connected components are 
3->1, 5->9->7->4->6 and 2->8.
Therefore, our answer is 3 
followed by 2 8 22, 3 1 66, 5 6 10.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function solve() which takes an integer n(the number of houses), p(the number of pipes),the array a[] , b[] and d[] (where d[i] denoting the diameter of the ith pipe from the house a[i] to house b[i]) as input parameter and returns the array of pairs of tanks and taps installed i.e ith element of the array contains three integers: house number of tank, house number of tap and the minimum diameter of pipe between them. Note that, returned array must be sorted based on the house number containing a tank (i.e. smaller house number should come before a large house number).
 
Expected Time Complexity: O(n+p)
Expected Auxiliary Space: O(n+p)
 
Constraints:
1<=n<=20
1<=p<=50
1<=a[i],b[i]<=20
1<=d[i]<=100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Graph traversal

Greedy algorithms

Starter code: #User function Template for python3

class Solution:

    def solve(self, n, p ,a, b, d): 

        #code here

Solutions:
from collections import defaultdict
from sys import maxsize

class Solution:

	def dfs(self, node, visited, adj, diameter, last_node):
		visited[node] = 1
		for (nbr, d) in adj[node]:
			if visited[nbr] == -1:
				diameter[0] = min(diameter[0], d)
				last_node[0] = nbr
				self.dfs(nbr, visited, adj, diameter, last_node)

	def solve(self, n, p, a, b, d):
		adj = defaultdict(list)
		indeg = defaultdict(int)
		for i in range(p):
			adj[a[i]].append((b[i], d[i]))
			indeg[b[i]] += 1
		visited = [-1] * (n + 1)
		ans = []
		for i in range(1, n + 1):
			if visited[i] == -1 and indeg[i] == 0:
				diameter = [maxsize]
				last_node = [i]
				self.dfs(i, visited, adj, diameter, last_node)
				if i != last_node[0]:
					ans.append([i, last_node[0], diameter[0]])
		ans.sort(key=lambda x: x[0])
		return ans


class Solution:

	def solve(self, n, p, a, b, d):
		index = 0
		while index < len(a):
			for (ind, i) in enumerate(a):
				if i == b[index]:
					td = d[ind] if d[ind] < d[index] else d[index]
					b[index] = b[ind]
					d[index] = td
					a = a[0:ind] + a[ind + 1:]
					b = b[0:ind] + b[ind + 1:]
					d = d[0:ind] + d[ind + 1:]
					break
			else:
				index = index + 1
		r = []
		for i in range(len(a)):
			r.append([a[i], b[i], d[i]])
		r = sorted(r, key=lambda x: x[0])
		return r


class Solution:

	def find(self, k, wt, end):
		temp = end[k]
		ans = wt[k]
		while end[temp] >= 0:
			ans = min(ans, wt[temp])
			temp = end[temp]
		return (temp, ans)

	def solve(self, n, p, a, b, d):
		end = [-1] * (n + 1)
		start = [-1] * (n + 1)
		wt = [-1] * (n + 1)
		for i in range(p):
			end[a[i]] = b[i]
			start[b[i]] = a[i]
			wt[a[i]] = d[i]
		sol = []
		for i in range(1, n + 1):
			if start[i] == -1 and end[i] >= 1:
				(j, ans) = self.find(i, wt, end)
				sol.append([i, j, ans])
		return sol


from collections import *
from sys import maxsize

class Solution:

	def dfs(self, node, visited, adj_list, end_node, mini):
		visited[node] = 1
		for (nbr, d) in adj_list[node]:
			if visited[nbr] == -1:
				mini[0] = min(mini[0], d)
				end_node[0] = nbr
				self.dfs(nbr, visited, adj_list, end_node, mini)

	def solve(self, n, p, a, b, d):
		adj_list = defaultdict(list)
		indeg = defaultdict(int)
		for i in range(p):
			adj_list[a[i]].append((b[i], d[i]))
			indeg[b[i]] += 1
		visited = [-1] * (n + 1)
		ans = []
		cnt = 0
		for i in range(1, n + 1):
			if visited[i] == -1 and indeg[i] == 0 and adj_list.get(i):
				cnt += 1
				mini = [maxsize]
				end_node = [i]
				self.dfs(i, visited, adj_list, end_node, mini)
				ans.append([i, end_node[0], mini[0]])
		ans.sort(key=lambda x: x[0])
		return ans


from collections import deque

class Solution:

	def solve(self, n, p, a, b, d):
		adj = [[] for _ in range(n + 1)]
		visit = [0] * (n + 1)
		indegree = [0] * (n + 1)
		for i in range(p):
			adj[a[i]].append([b[i], d[i]])
			indegree[b[i]] += 1

		def fun(i):
			visit[i] = 1
			q = deque()
			q.append(i)
			w = 1000
			while q:
				t = q.popleft()
				for j in adj[t]:
					if visit[j[0]] == 0:
						visit[j[0]] = 1
						q.append(j[0])
						w = min(w, j[1])
			return [i, t, w]
		ans = []
		for i in range(1, n + 1):
			if visit[i] == 0 and indegree[i] == 0 and (len(adj[i]) > 0):
				ans.append(fun(i))
		return ans


class Solution:

	def solve(self, n, p, a, b, d):
		from math import inf
		(st, en, pp) = ([0] * (n + 1), [0] * (n + 1), [0] * (n + 1))
		for i in range(p):
			(start, end, w) = (a[i], b[i], d[i])
			st[start] = end
			en[end] = start
			pp[start] = w

		def dfs(i, ans):
			if st[i] == 0:
				return (i, ans)
			if ans > pp[i]:
				ans = pp[i]
			return dfs(st[i], ans)
		x = []
		for i in range(1, n + 1):
			if st[i] and en[i] == 0:
				ans = inf
				(e, ans) = dfs(i, ans)
				x.append([i, e, ans])
		x.sort()
		return x


class Solution:

	def solve(self, n, p, a, b, d):
		(tanks, nex) = ([True] * (n + 1), [None] * (n + 1))
		for (src, dst, dia) in zip(a, b, d):
			nex[src] = (dst, dia)
			tanks[dst] = False
		ans = []
		for src in range(1, n + 1):
			if not tanks[src]:
				continue
			dst = src
			mn = 10 ** 9
			while nex[dst] is not None:
				(dst, dia) = nex[dst]
				mn = min(mn, dia)
			if dst != src:
				ans.append((src, dst, mn))
		return ans


class Solution:

	def solve(self, n, p, a, b, d):
		visited = set()
		ans = []
		inlet = [0] * (n + 1)
		outlet = [0] * (n + 1)
		graph = [[] for i in range(n + 1)]
		for i in range(0, p):
			outlet[a[i]] = 1
			inlet[b[i]] = 1
			graph[a[i]].append([b[i], d[i]])

		def dfs(node, end, min_dia):
			visited.add(node)
			for neigh in graph[node]:
				if neigh[0] not in visited:
					min_dia[0] = min(min_dia[0], neigh[1])
					end[0] = neigh[0]
					i = neigh[0]
					dfs(i, end, min_dia)
			return
		for i in range(1, n + 1):
			if inlet[i] == 0 and outlet[i] == 1 and (i not in visited):
				start = i
				end = [-1]
				min_dia = [10000000000.0]
				dfs(i, end, min_dia)
				ans.append([start, end[0], min_dia[0]])
		return ans


from collections import defaultdict
import sys

class Solution:

	def solve(self, n, p, a, b, d):

		def dfs(u, find):
			vis[u] = 1
			for item in graph[u]:
				(v, w) = item
				if vis[v] == 0:
					find[0] = v
					find[1] = min(w, find[1])
					dfs(v, find)
		In = [0] * (n + 1)
		Out = [0] * (n + 1)
		graph = defaultdict(list)
		for i in range(0, p):
			In[b[i]] = 1
			Out[a[i]] = 1
			graph[a[i]].append((b[i], d[i]))
		vis = [0] * (n + 1)
		ans = []
		cnt = 0
		for i in range(0, n + 1):
			if In[i] == 0 and Out[i] == 1 and (vis[i] == 0):
				start = i
				find = [-1, sys.maxsize]
				dfs(i, find)
				ans.append((start, find[0], find[1]))
		ans.sort()
		return ans


class Solution:

	def dfs(self, v, out, inn, wt, ans):
		if out[v] == 0:
			ans[-1][1] = v
			return
		ans[-1][2] = min(ans[-1][2], wt[v])
		self.dfs(out[v], out, inn, wt, ans)

	def solve(self, n, p, a, b, d):
		out = [0] * (n + 1)
		inn = [0] * (n + 1)
		wt = [0] * (n + 1)
		for i in range(p):
			out[a[i]] = b[i]
			inn[b[i]] = a[i]
			wt[a[i]] = d[i]
		ans = []
		for i in range(1, n + 1):
			if inn[i] == 0 and out[i]:
				ans.append([i, -1, wt[i]])
				self.dfs(i, out, inn, wt, ans)
		return ans


def dfs(v, out, inc, wei, t):
	if out[v] == 0:
		t[-1][1] = v
		return
	t[-1][2] = min(t[-1][2], wei[v])
	dfs(out[v], out, inc, wei, t)

class Solution:

	def solve(self, n, p, a, b, d):
		out = [0] * (n + 1)
		inc = [0] * (n + 1)
		wei = [0] * (n + 1)
		for i in range(p):
			out[a[i]] = b[i]
			inc[b[i]] = a[i]
			wei[a[i]] = d[i]
		t = []
		for i in range(1, n + 1):
			if inc[i] == 0 and out[i]:
				t.append([i, -1, wei[i]])
				dfs(i, out, inc, wei, t)
		return t


class Solution:

	def solve(self, n, p, a, b, d):
		df = {}
		db = {}
		dv = {}
		for i in range(p):
			df[a[i]] = b[i]
			db[b[i]] = a[i]
			if a[i] not in dv:
				dv[a[i]] = d[i]
			else:
				dv[a[i]] = min(dv[a[i]], d[i])
			if b[i] not in dv:
				dv[b[i]] = d[i]
			else:
				dv[b[i]] = min(dv[b[i]], d[i])

		def pro(i, dic, val, vis):
			if i not in dic:
				vis[i] = 0
				return i
			vis[i] = 0
			res = pro(dic[i], dic, val, vis)
			mini = min(val[dic[i]], val[i])
			val[i] = mini
			return res
		vis = [1] * (n + 1)
		res = []
		for i in range(1, n + 1):
			if vis[i] and i in dv and (i not in db):
				tres = []
				tres.append(i)
				tres.append(pro(i, df, dv, vis))
				tres.append(dv[i])
				res.append(tres)
		return res


from collections import defaultdict

class Solution:

	def solve(self, n, p, a, b, d):
		g = defaultdict(lambda : [])
		ind = [0] * (n + 1)
		for i in range(p):
			g[a[i]].append((b[i], d[i]))
			ind[b[i]] = 1
		visited = [False] * (n + 1)

		def dfs(u, minc):
			visited[u] = True
			for (v, dist) in g[u]:
				if not visited[v]:
					temp = dfs(v, min(minc, dist))
					minc = min(minc, temp[1])
					return [temp[0], minc]
			return [u, minc]
		ans = []
		for i in range(1, n + 1):
			if i in g and (not visited[i]) and (ind[i] == 0):
				temp = dfs(i, float('inf'))
				ans.append([i, temp[0], temp[1]])
		return ans


class Solution:

	def solve(self, n, p, a, b, d):

		def dfs(node, start, adj, ans, d):
			if len(adj[node]) == 0:
				ans.append([start, node, d])
				return
			for [i, j] in adj[node]:
				dfs(i, start, adj, ans, min(d, j))
			return
		s = set()
		ans = []
		adj = [[] for i in range(n + 1)]
		for i in range(p):
			adj[a[i]].append([b[i], d[i]])
			s.add(a[i])
		for i in b:
			if i in s:
				s.remove(i)
		for j in s:
			dfs(j, j, adj, ans, float('inf'))
		return ans


class Solution:

	def solve(self, n, p, a, b, d):
		ax = {}
		bx = {}
		for i in range(p):
			ax[a[i]] = i
			bx[b[i]] = i
		start = []
		for i in a:
			if i not in bx:
				start.append(i)
		ans = []
		for i in start:
			root = i
			index = ax[i]
			mn = d[index]
			while True:
				index = ax[i]
				mn = min(d[index], mn)
				if b[index] not in ax:
					ans.append([root, b[index], mn])
					break
				else:
					i = b[index]
		ans.sort()
		return ans


class Solution:

	def dfs(self, i, start, end, wieght, ans):
		if not start[i]:
			return i
		ans[0] = min(ans[0], wieght[i])
		return self.dfs(start[i], start, end, wieght, ans)

	def solve(self, n, p, a, b, d):
		start = [0] * (n + 1)
		end = [0] * (n + 1)
		wieght = [0] * (n + 1)
		for i in range(p):
			start[a[i]] = b[i]
			end[b[i]] = a[i]
			wieght[a[i]] = d[i]
		res = []
		for i in range(1, n + 1):
			ans = [10 ** 10]
			if start[i] and (not end[i]):
				endcomponent = self.dfs(i, start, end, wieght, ans)
				res.append([i, endcomponent, ans[0]])
		return res


from collections import deque

class Solution:

	def adjFromPairs(self, n, p, a, b, d):
		res = [[] for i in range(n)]
		heads = [True] * n
		harr = []
		for i in range(p):
			res[a[i] - 1].append([b[i] - 1, d[i]])
			heads[b[i] - 1] = False
		for i in range(n):
			if heads[i]:
				harr.append(i)
		return (res, harr)

	def solve(self, n, p, a, b, d):
		(adj, roots) = self.adjFromPairs(n, p, a, b, d)
		visited = [False] * n
		res = []
		for i in roots:
			minD = 100000000.0
			leaf = -1
			visited[i] = True
			q = deque()
			q.append((i, 100000000.0))
			while q:
				c = q.popleft()
				if c[1] < minD:
					minD = c[1]
				if len(adj[c[0]]) == 0:
					leaf = c[0]
					continue
				for ne in adj[c[0]]:
					if not visited[ne[0]]:
						q.append(ne)
						visited[ne[0]] = True
			if i != leaf:
				res.append((i + 1, leaf + 1, minD))
		return res


import sys

class Solution:

	def DFS(self, u, starting_vertex, ending_vertex, diameter, temp_dia):
		if starting_vertex[u] == 0:
			return u
		if diameter[u] < temp_dia[0]:
			temp_dia[0] = diameter[u]
		return self.DFS(starting_vertex[u], starting_vertex, ending_vertex, diameter, temp_dia)

	def solve(self, n, p, a, b, d):
		starting_vertex = [0 for i in range(1000)]
		ending_vertex = [0 for i in range(1000)]
		diameter = [0 for i in range(1000)]
		ans = []
		for i in range(len(a)):
			starting_vertex[a[i]] = b[i]
			diameter[a[i]] = d[i]
			ending_vertex[b[i]] = a[i]
		for i in range(1, n + 1):
			if ending_vertex[i] == 0 and starting_vertex[i]:
				temp_dia = [sys.maxsize]
				end = self.DFS(i, starting_vertex, ending_vertex, diameter, temp_dia)
				ans.append([i, end, temp_dia[0]])
		ans.sort()
		return ans


class Solution:

	def solve(self, n, p, a, b, d):
		global ans

		def dfs(w):
			global ans
			if out_h[w] == 0:
				return w
			if wt_h[w] < ans:
				ans = wt_h[w]
			return dfs(out_h[w])
		in_h = [0] * 1000
		out_h = [0] * 1000
		wt_h = [0] * 1000
		l1 = []
		l2 = []
		for i in range(p):
			from_h = a[i]
			to_h = b[i]
			p_h = d[i]
			out_h[from_h] = to_h
			wt_h[from_h] = p_h
			in_h[to_h] = from_h
		for j in range(1, n + 1):
			l1 = []
			if in_h[j] == 0 and out_h[j]:
				ans = 1000000000
				w = dfs(j)
				l1.append(j)
				l1.append(w)
				l1.append(ans)
				l2.append(l1)
		return l2


class Solution:

	def solve(self, n, p, a, b, d):

		def dfs(i, g, mv, e, vis, ans):
			vis[i] = 1
			if len(g[i]) != 0 and vis[g[i][0]] == 0:
				e = g[i][0]
				mv = min(g[i][1], mv)
				dfs(g[i][0], g, mv, e, vis, ans)
			else:
				ans.append([s, e, mv])
		inp = [0] * (n + 1)
		out = [0] * (n + 1)
		vis = [0] * (n + 1)
		g = [[]] * (n + 1)
		ans = []
		for i in range(p):
			inp[b[i]] = 1
			out[a[i]] = 1
			g[a[i]] = [b[i], d[i]]
		for i in range(n + 1):
			if inp[i] == 0 and out[i] == 1 and (vis[i] == 0):
				s = i
				e = 0
				mv = float('inf')
				dfs(i, g, mv, e, vis, ans)
		return ans


class Solution:

	def solve(self, n, p, a, b, d):
		visited = [False] * n
		adj = [None] * n
		ind = [0] * n
		out = [0] * n
		for i in range(p):
			adj[a[i] - 1] = (b[i] - 1, d[i])
			ind[b[i] - 1] += 1
			out[a[i] - 1] += 1
		start = []
		res = []
		for v in range(n):
			if ind[v] == 0 and out[v] == 1:
				start.append(v)
		for s in start:
			q = s
			pd = 1000
			while adj[q]:
				(nxt, di) = adj[q]
				q = nxt
				pd = min(pd, di)
			res.append([s + 1, q + 1, pd])
		return res


class Solution:

	def solve(self, n, p, a, b, d):
		adj = [() for i in range(n + 1)]
		indeg = [0] * (n + 1)
		for (u, v, w) in zip(a, b, d):
			adj[u] = (v, w)
			indeg[v] += 1
		res = []
		for u in range(1, n + 1):
			if indeg[u] == 0 and adj[u]:
				res.append([u, u, 0])
		for i in range(len(res)):
			(u, v, w) = res[i]
			(dest, wei) = adj[u]
			while adj[dest]:
				(dest1, wei1) = adj[dest]
				(dest, wei) = (dest1, min(wei1, wei))
			res[i] = [u, dest, wei]
		return res


class Graph:

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

	def add_pipe(self, house_a, house_b, distance):
		self.graph[house_a] = (house_b, distance)

	def utils_DFS(self, key, minimum):
		if not self.graph.get(key):
			return key
		if minimum[0] > self.graph[key][1]:
			minimum[0] = self.graph[key][1]
		return self.utils_DFS(self.graph[key][0], minimum)

class Solution:

	def solve(self, n, p, a, b, d):
		g1 = Graph()
		for i in range(p):
			g1.add_pipe(a[i], b[i], d[i])
		ref = {}
		for h_b in b:
			ref[h_b] = 1
		res = []
		a.sort()
		for h_a in a:
			if not ref.get(h_a):
				minimum = [float('inf')]
				h_b = g1.utils_DFS(h_a, minimum)
				res.append((h_a, h_b, minimum[0]))
		return res


starting_vertices = None
ending_vertices = None
diameters = None

class Solution:

	def dfs(self, u, ans):
		if starting_vertices[u] == 0:
			return u
		if diameters[u] < ans[0]:
			ans[0] = diameters[u]
		return self.dfs(starting_vertices[u], ans)

	def solve(self, n, p, a, b, d):
		global starting_vertices, ending_vertices, diameters
		starting_vertices = [0] * (n + 1)
		diameters = [0] * (n + 1)
		ending_vertices = [0] * (n + 1)
		for i in range(p):
			house1 = a[i]
			diameter = d[i]
			house2 = b[i]
			starting_vertices[house1] = house2
			diameters[house1] = d[i]
			ending_vertices[house2] = house1
		res = []
		for u in range(1, n + 1):
			if ending_vertices[u] == 0 and starting_vertices[u] != 0:
				ans = [1 << 63]
				v = self.dfs(u, ans)
				res.append([u, v, ans[0]])
		res.sort(key=lambda item: item[0])
		return res


class Solution:

	def solve(self, n, p, a, b, d):
		graph = dict()
		for (src, dst, diam) in zip(a, b, d):
			graph[src] = (dst, diam)
		startNodes = sorted(list(set(a).difference(set(b))))
		res = []
		for node in startNodes:
			v = node
			minDiam = float('inf')
			while True:
				minDiam = min(graph[v][1], minDiam)
				v = graph[v][0]
				if v not in graph.keys():
					break
			res.append((node, v, minDiam))
		return res


class Solution:

	def solve(self, n, p, a, b, d):
		ans = [[a[0], b[0], d[0]]]
		a.pop(0)
		b.pop(0)
		d.pop(0)
		while a:
			if ans[-1][1] in a:
				index = a.index(ans[-1][1])
				ans[-1][1] = b[index]
				ans[-1][2] = min(ans[-1][2], d[index])
				a.pop(index)
				b.pop(index)
				d.pop(index)
			elif ans[-1][0] in b:
				index = b.index(ans[-1][0])
				ans[-1][0] = a[index]
				ans[-1][2] = min(ans[-1][2], d[index])
				a.pop(index)
				b.pop(index)
				d.pop(index)
			elif a:
				ans.append([a[0], b[0], d[0]])
				a.pop(0)
				b.pop(0)
				d.pop(0)
		for i in ans:
			if i[0] == i[1]:
				ans.remove(i)
		ans.sort()
		return ans


from collections import defaultdict

class Solution:

	def solve(self, n, p, a, b, d):
		visited = defaultdict(lambda : False)
		matrix = defaultdict(list)
		indegree = defaultdict(lambda : 0)
		for (ai, bi, di) in zip(a, b, d):
			matrix[ai].append([bi, di])
			indegree[bi] += 1

		def dfs(node):
			ans = float('inf')
			v = None
			for (n, c) in matrix[node]:
				if not visited[n]:
					visited[n] = True
					(ans, v) = dfs(n)
					ans = min(c, ans)
			v = node if v is None else v
			return (ans, v)
		ans = []
		for i in range(1, n + 1):
			if not visited[i] and (not indegree[i]):
				visited[i] = True
				(cost, enode) = dfs(i)
				if cost == float('inf'):
					continue
				ans.append([i, enode, cost])
		return ans


def dfs(w, cd, wt, ans):
	if cd[w] == 0:
		return (w, ans)
	if wt[w] < ans:
		ans = wt[w]
	return dfs(cd[w], cd, wt, ans)

class Solution:

	def solve(self, n, p, a, b, d):
		cd = [0 for i in range(n + 1)]
		rd = [0 for i in range(n + 1)]
		wt = [-1 for i in range(n + 1)]
		for i in range(0, len(a)):
			cd[a[i]] = b[i]
			rd[b[i]] = a[i]
			wt[a[i]] = d[i]
		res = []
		for i in range(1, n + 1):
			if rd[i] == 0 and cd[i] != 0:
				p = dfs(i, cd, wt, 1000000)
				res.append((i, p[0], p[1]))
		return sorted(res, key=lambda x: x[0])


class Solution:

	def __init__(self):
		self.ans = 0

	def dfs(self, i, s, t, e):
		global ans
		if s[i] == 0:
			return i
		if t[i] < self.ans:
			self.ans = t[i]
		return self.dfs(s[i], s, t, e)

	def solve(self, n, p, a, b, d):
		s = [0] * (n + 1)
		e = [0] * (n + 1)
		t = [0] * (n + 1)
		for i in range(p):
			s[a[i]] = b[i]
			t[a[i]] = d[i]
			e[b[i]] = a[i]
		output = []
		for i in range(1, n + 1):
			m = []
			if e[i] == 0 and s[i]:
				self.ans = 1000000000
				end = self.dfs(i, s, t, e)
				m.append(i)
				m.append(end)
				m.append(self.ans)
				output.append(m)
		return output


class Solution:

	def solve(self, n, p, a, b, d):
		from collections import defaultdict
		g = defaultdict(list)
		for i in range(len(a)):
			g[a[i]].append([b[i], d[i]])
		in_count = [0] * (n + 1)
		out_count = [0] * (n + 1)
		for val in b:
			in_count[val] += 1
		for val in a:
			out_count[val] += 1

		def dfs(node, curMin):
			if self.aa >= curMin:
				self.aa = curMin
				self.finale = node
			self.visited.add(node)
			for (nei, price) in g[node]:
				if nei not in self.visited:
					self.visited.add(nei)
					dfs(nei, min(curMin, price))
		self.visited = set()
		t = 0
		de = []
		for (cur, val) in enumerate(in_count):
			if cur == 0:
				continue
			self.aa = float('inf')
			self.finale = None
			if val == 0 and out_count[cur] != 0:
				t += 1
				dfs(cur, self.aa)
				de.append([cur, self.finale, self.aa])
		return de


class Solution:

	def solve(self, n, p, a, b, d):
		stack = []
		start = {}
		end = {}
		diameter = {}
		ans = []
		temp = []
		for i in range(p):
			start[a[i]] = b[i]
			end[b[i]] = a[i]
			diameter[a[i]] = d[i]
		for i in range(1, n + 1):
			if i not in end and i in start:
				stack.append(start[i])
				s = i
				d = diameter[i]
				e = 0
				while stack:
					x = stack.pop()
					if x not in start:
						e = x
					else:
						if diameter[x] < d:
							d = diameter[x]
						stack.append(start[x])
				ans.append([s, e, d])
		return ans


class Solution:
	e = 0
	m = -1

	def solve(self, n, p, a, b, d):
		inarr = [0] * 21
		outarr = [0] * 21
		g = {}
		vis = [0] * (n + 1)
		ans = []
		for i in range(0, p):
			inarr[b[i]] = 1
			outarr[a[i]] = 1
			g[a[i]] = [b[i], d[i]]
		for i in range(1, n + 1):
			if inarr[i] == 0 and outarr[i] == 1 and (vis[i] == 0):
				s = i
				self.e = -1
				self.m = 1000
				self.dfs(s, self.e, self.m, g, vis)
				ans.append([s, self.e, self.m])
		return ans

	def dfs(self, s, e, m, g, vis):
		vis[s] = 1
		if s in g:
			node = g[s][0]
			if vis[node] == 0:
				self.e = g[s][0]
				self.m = min(m, g[s][1])
				self.dfs(g[s][0], self.e, self.m, g, vis)


from collections import defaultdict

class Solution:

	def solve(self, n, p, a, b, d):
		vis = set()

		def dfs(e, c):
			vis.add(e)
			for (neigh, d) in adj[e]:
				if neigh not in vis:
					(e, c) = dfs(neigh, min(c, d))
			return (e, c)
		inarr = [0] * n
		outarr = [0] * n
		adj = defaultdict(lambda : list())
		for i in range(p):
			s = a[i]
			e = b[i]
			c = d[i]
			adj[s].append((e, c))
			outarr[s - 1] = 1
			inarr[e - 1] = 1
		res = []
		for i in range(n):
			if not inarr[i] and outarr[i] and (i + 1 not in vis):
				res.append((i + 1, *dfs(i + 1, float('inf'))))
		return res


class Solution:

	def solve(self, n, p, a, b, d):
		adj = [-1 for i in range(n + 1)]
		ind = [0 for i in range(n + 1)]
		for i in range(p):
			adj[a[i]] = [b[i], d[i]]
			ind[b[i]] += 1

		def f(cn, tans):
			if adj[cn] == -1:
				return cn
			tans[0] = min(tans[0], adj[cn][1])
			temp = f(adj[cn][0], tans)
			return temp
		ans = []
		from sys import maxsize
		for i in range(1, n + 1):
			if ind[i] == 0 and adj[i] != -1:
				a1 = i
				tans = [maxsize]
				a2 = f(i, tans)
				a3 = tans[0]
				ans.append([a1, a2, a3])
		ans.sort(key=lambda x: x[0])
		return ans


class Graph:

	def __init__(self):
		self.NODE_COUNT = 0
		self.EDGE_COUNT = 0
		self.ADJ_LIST = dict()
		self.EDGE_DICT = dict()
		self.IN_DEGREE = dict()

	def addNode(self, node):
		if node not in self.ADJ_LIST:
			self.ADJ_LIST[node] = list()
			self.NODE_COUNT += 1
			self.IN_DEGREE[node] = 0

	def addEdge(self, node1, node2, weight):
		if node1 not in self.ADJ_LIST:
			self.addNode(node1)
		if node2 not in self.ADJ_LIST:
			self.addNode(node2)
		self.ADJ_LIST[node1].append(node2)
		self.EDGE_COUNT += 1
		self.EDGE_DICT[node2] = weight
		self.IN_DEGREE[node2] += 1

	def dfsUtil(self):
		op = list()
		visitedDict = {node: False for node in self.ADJ_LIST}
		getZeroIndegree = list()
		for node in self.IN_DEGREE:
			if self.IN_DEGREE[node] == 0:
				getZeroIndegree.append(node)
		for node in getZeroIndegree:
			if visitedDict[node] == False:
				temp = [node]
				minDiameter = float('inf')
				self.dfs(node, visitedDict, temp, minDiameter)
				op.append(temp)
		return op

	def dfs(self, node, visitedDict, temp, minDiameter):
		visitedDict[node] = True
		for neighbourNode in self.ADJ_LIST[node]:
			if visitedDict[neighbourNode] == False:
				minDiameter = min(minDiameter, self.EDGE_DICT[neighbourNode])
				self.dfs(neighbourNode, visitedDict, temp, minDiameter)
		if len(self.ADJ_LIST[node]) == 0:
			temp.append(node)
			temp.append(minDiameter)

class Solution:

	def solve(self, n, p, a, b, d):
		graph = Graph()
		for index in range(p):
			graph.addEdge(a[index], b[index], d[index])
		return graph.dfsUtil()


class Solution:

	def solve(self, n, p, a, b, d):
		adj = [[] for _ in range(n + 1)]
		s = set()
		ans = []
		for i in range(p):
			adj[a[i]].append([b[i], d[i]])
			s.add(a[i])
		for i in range(p):
			if b[i] in s:
				s.remove(b[i])

		def dfs(u, start, mi, ans):
			if len(adj[u]) == 0:
				ans.append([start, u, mi])
				return
			for (v, w) in adj[u]:
				dfs(v, start, min(mi, w), ans)
				return
		for u in s:
			dfs(u, u, float('inf'), ans)
		return ans


from collections import defaultdict

class Solution:

	def solve(self, n, p, a, b, d):
		son = defaultdict(list)
		par = defaultdict(int)
		for i in range(len(a)):
			son[a[i]] = [b[i], d[i]]
			par[b[i]] = a[i]
		vis = [0] * (n + 1)
		ans = []
		count = 0

		def bfs(i):
			queue = [[i, float('inf')]]
			res = [i, 0, float('inf')]
			while queue:
				s = queue.pop(0)
				res[2] = min(res[2], s[1])
				if son.get(s[0]):
					queue.append(son.get(s[0]))
				else:
					res[1] = s[0]
					return res
		for i in range(1, n + 1):
			if par.get(i) or vis[i] == 1:
				continue
			if not par.get(i) and (not son.get(i)):
				continue
			ans.append(bfs(i))
			count += 1
		return ans


import sys

class Solution:

	def dfs(self, graph, vis, src, end, di):
		vis[src] = True
		if src in graph.keys():
			for x in graph[src]:
				if not vis[x[0]]:
					end[0] = x[0]
					di[0] = min(di[0], x[1])
					self.dfs(graph, vis, x[0], end, di)

	def solve(self, n, p, a, b, d):
		graph = {}
		In = [0] * (n + 1)
		Out = [0] * (n + 1)
		Visited = [False] * (n + 1)
		ans = []
		for i in range(p):
			Out[a[i]] = 1
			In[b[i]] = 1
			graph[a[i]] = [(b[i], d[i])]
		for i in range(1, n + 1):
			if In[i] == 0 and Out[i] == 1 and (not Visited[i]):
				start = i
				end = [0]
				minidi = [sys.maxsize]
				self.dfs(graph, Visited, i, end, minidi)
				ans.append([start, end[0], minidi[0]])
		return ans


from math import inf

class Solution:

	def solve(self, n, p, a, b, d):

		def f(i):
			nonlocal mi
			if x[i] == None:
				nonlocal ans
				ans = i
				return
			nonlocal mi
			(a, b) = x[i]
			mi = min(mi, b)
			f(a)
		x = [None for i in range(n)]
		se = set((i for i in range(n)))
		for i in range(p):
			x[b[i] - 1] = (a[i] - 1, d[i])
			if a[i] - 1 in se:
				se.remove(a[i] - 1)
		res = []
		for i in se:
			ans = None
			mi = inf
			f(i)
			if mi != inf:
				res.append((ans + 1, i + 1, mi))
		return sorted(res)


class Solution:

	def solve(self, n, p, a, b, d):
		(ans, source) = ([], list(set(a) - set(b)))
		dic = {a[i]: (b[i], d[i]) for i in range(p)}
		source.sort()
		for s in source:
			e = dic[s]
			(one, two, three) = (s, e[0], e[1])
			while two in dic:
				e = dic[two]
				(two, three) = (e[0], min(three, e[1]))
			ans.append([one, two, three])
		return ans


class Solution:

	def solve(self, n, p, a, b, d):
		visited = [0 for _ in range(n + 1)]
		adj = [-1 for _ in range(n + 1)]
		inc = [0 for _ in range(n + 1)]
		outg = [0 for _ in range(n + 1)]
		for (ai, bi, di) in zip(a, b, d):
			adj[ai] = (bi, di)
			outg[ai] += 1
			inc[bi] += 1

		def recur_comp_cost(node, min_so_far):
			visited[node] = 1
			if adj[node] != -1 and (not visited[adj[node][0]]):
				cost = adj[node][1]
				neigh = adj[node][0]
				return recur_comp_cost(neigh, min(cost, min_so_far))
			return (node, min_so_far)
		ans = []
		for node in range(1, n + 1):
			if not visited[node] and adj[node] != -1 and (inc[node] == 0):
				temp = [node]
				(tap, min_cost) = recur_comp_cost(node, adj[node][1])
				temp.append(tap)
				temp.append(min_cost)
				ans.append(temp)
		return ans


from queue import Queue
ans = 0

def dfs(i, start, end, value):
	global ans
	if i not in start:
		return i
	if value[i] < ans:
		ans = value[i]
	return dfs(start[i], start, end, value)

class Solution:

	def solve(self, n, p, a, b, d):
		global ans
		start = {}
		end = {}
		value = {}
		l = []
		for i in range(p):
			start[a[i]] = b[i]
			end[b[i]] = a[i]
			value[a[i]] = d[i]
		for i in start:
			if i not in end:
				ans = 100000000
				result = dfs(i, start, end, value)
				l.append([i, result, ans])
		l.sort(key=lambda x: x[0])
		return l


import sys
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict

class Solution:

	def solve(self, n, p, a, b, d):
		self.graph = defaultdict(list)
		self.indegree = [0] * n
		self.outdegree = [0] * n
		for i in range(p):
			self.graph[a[i] - 1].append((b[i] - 1, d[i]))
			self.indegree[b[i] - 1] += 1
			self.outdegree[a[i] - 1] += 1
		res = []
		self.visited = [False] * n
		for i in range(n):
			if not self.visited[i] and self.indegree[i] == 0 and (self.outdegree[i] == 1):
				order = []
				diams = []
				self.dfs(i, order, diams)
				res.append([order[0] + 1, order[-1] + 1, min(diams)])
		return res

	def dfs(self, v, order, diams):
		self.visited[v] = True
		order.append(v)
		for (neigh, cost) in self.graph[v]:
			if not self.visited[neigh]:
				diams.append(cost)
				self.dfs(neigh, order, diams)


class Solution:

	def dfs(self, i, adj):
		self.vis[i] = 1
		if len(adj[i]) == 0:
			self.dis = min(self.dis, self.dic[i + 1])
			self.fin = i
			return
		for j in adj[i]:
			if self.vis[j] == 0:
				self.dis = min(self.dis, self.dic[j + 1])
				self.dfs(j, adj)

	def solve(self, n, p, a, b, d):
		ans = []
		st = [i for i in a if i not in b]
		self.dic = {}
		for i in range(p):
			self.dic[b[i]] = d[i]
		adj = [[] for i in range(n)]
		for i in range(p):
			adj[a[i] - 1].append(b[i] - 1)
		self.vis = [0] * n
		st.sort()
		for i in st:
			i -= 1
			if self.vis[i] == 0:
				self.fin = -1
				self.dis = 100
				self.dfs(i, adj)
			ans.append([i + 1, self.fin + 1, self.dis])
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, p) = map(int, input().strip().split())
		a = []
		b = []
		d = []
		for i in range(p):
			(x, y, z) = map(int, input().strip().split())
			a.append(x)
			b.append(y)
			d.append(z)
		ob = Solution()
		ans = ob.solve(n, p, a, b, d)
		print(len(ans))
		for i in ans:
			print(str(i[0]) + ' ' + str(i[1]) + ' ' + str(i[2]))


class Solution:

	def solve(self, n, p, a, b, d):
		adjList = dict()
		inRight = set(b)
		possibleRoots = list()
		for i in range(p):
			adjList[a[i]] = (b[i], d[i])
			if a[i] not in inRight:
				possibleRoots.append(a[i])
		possibleRoots.sort()
		tot = list()
		stack = list()
		for i in range(len(possibleRoots)):
			stack.append(possibleRoots[i])
			minRad = 100000000000000
			temp = [possibleRoots[i]]
			while stack:
				popped = stack.pop()
				if not popped in adjList:
					continue
				stack.append(adjList[popped][0])
				minRad = min(minRad, adjList[popped][1])
			temp.extend([popped, minRad])
			tot.append(temp)
		return tot
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, p) = map(int, input().strip().split())
		a = []
		b = []
		d = []
		for i in range(p):
			(x, y, z) = map(int, input().strip().split())
			a.append(x)
			b.append(y)
			d.append(z)
		ob = Solution()
		ans = ob.solve(n, p, a, b, d)
		print(len(ans))
		for i in ans:
			print(str(i[0]) + ' ' + str(i[1]) + ' ' + str(i[2]))


class Solution:

	def dfs(self, node, visited, graph):
		visited[node] = True
		for (nei, wt) in graph[node]:
			if visited[nei] == False:
				self.end = nei
				self.mini = min(self.mini, wt)
				self.dfs(nei, visited, graph)

	def solve(self, n, p, a, b, d):
		import sys
		from collections import defaultdict
		graph = defaultdict(list)
		for i in range(p):
			graph[a[i]].append((b[i], d[i]))
		incoming_pipe = [0] * (n + 1)
		outgoing_pipe = [0] * (n + 1)
		for i in range(p):
			incoming_pipe[b[i]] += 1
			outgoing_pipe[a[i]] += 1
		visited = [False] * (n + 1)
		ans = []
		global end, mini
		for i in range(1, n + 1):
			if incoming_pipe[i] == 0 and outgoing_pipe[i] == 1 and (visited[i] == False):
				strt = i
				self.end = 0
				self.mini = sys.maxsize
				self.dfs(i, visited, graph)
				ans.append([strt, self.end, self.mini])
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, p) = map(int, input().strip().split())
		a = []
		b = []
		d = []
		for i in range(p):
			(x, y, z) = map(int, input().strip().split())
			a.append(x)
			b.append(y)
			d.append(z)
		ob = Solution()
		ans = ob.solve(n, p, a, b, d)
		print(len(ans))
		for i in ans:
			print(str(i[0]) + ' ' + str(i[1]) + ' ' + str(i[2]))


INT_MAX = 2 ** 32

def dfs(arr, start, tmp, visited):
	visited[start] = 1
	(w, c) = arr[start]
	if w != -1 and visited[w] == 0:
		mw = min(tmp[0], c)
		tmp[0] = mw
		tmp[1] = w
		dfs(arr, w, tmp, visited)

class Solution:

	def solve(self, n, p, a, b, d):
		ans = []
		arr = [(-1, -1) for i in range(n + 1)]
		visited = [0 for i in range(n + 1)]
		ina = [0 for i in range(n + 1)]
		out = [0 for i in range(n + 1)]
		for i in range(p):
			out[a[i]] = 1
			ina[b[i]] = 1
			arr[a[i]] = (b[i], d[i])
		for i in range(1, n + 1):
			if ina[i] == 0 and out[i] != 0 and (visited[i] == 0):
				start = i
				tmp = [INT_MAX, -1]
				dfs(arr, start, tmp, visited)
				ans.append([start, tmp[1], tmp[0]])
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, p) = map(int, input().strip().split())
		a = []
		b = []
		d = []
		for i in range(p):
			(x, y, z) = map(int, input().strip().split())
			a.append(x)
			b.append(y)
			d.append(z)
		ob = Solution()
		ans = ob.solve(n, p, a, b, d)
		print(len(ans))
		for i in ans:
			print(str(i[0]) + ' ' + str(i[1]) + ' ' + str(i[2]))


from collections import defaultdict

class Solution:

	def solve(self, n, p, a, b, d):
		graph = defaultdict(list)
		inc = [0] * (n + 1)
		out = [0] * (n + 1)
		for i in range(p):
			out[a[i]] = 1
			inc[b[i]] = 1
			graph[a[i]].append([b[i], d[i]])

		def dfs(node, visited):
			visited[node] = True
			for nei in graph[node]:
				if visited[nei[0]] == False:
					self.end = nei[0]
					self.dia = min(self.dia, nei[1])
					dfs(nei[0], visited)
		visited = [False] * (n + 1)
		self.start = -1
		self.end = -1
		self.dia = float('inf')
		ans = []
		for i in range(1, n + 1):
			if visited[i] == False and inc[i] == 0 and (out[i] == 1):
				self.start = i
				self.end = -1
				self.dia = float('inf')
				dfs(i, visited)
				ans.append([self.start, self.end, self.dia])
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, p) = map(int, input().strip().split())
		a = []
		b = []
		d = []
		for i in range(p):
			(x, y, z) = map(int, input().strip().split())
			a.append(x)
			b.append(y)
			d.append(z)
		ob = Solution()
		ans = ob.solve(n, p, a, b, d)
		print(len(ans))
		for i in ans:
			print(str(i[0]) + ' ' + str(i[1]) + ' ' + str(i[2]))


class Solution:

	def solve(self, n, p, a, b, d):
		adj = []
		exist = [False] * (n + 1)
		for i in range(n + 1):
			adj.append([])
		for i in range(p):
			exist[a[i]] = True
			exist[b[i]] = True
			adj[a[i]].append(b[i])
			adj[a[i]].append(d[i])
		indeg = [0] * (n + 1)
		for i in range(len(adj)):
			if len(adj[i]) > 0:
				(j, wt) = adj[i]
				indeg[j] = 1
		queue = []
		for i in range(len(indeg)):
			if indeg[i] == 0 and exist[i]:
				queue.append(i)

		def traverse(node, minn):
			if len(adj[node]) == 0:
				ans[-1].append(node)
				ans[-1].append(minn)
			elif visited[node] == False:
				visited[node] = True
				(nbr, wt) = adj[node]
				if minn > wt:
					minn = wt
				traverse(nbr, minn)
		ans = []
		visited = [False] * (n + 1)
		nop = len(queue)
		while queue:
			curr = queue.pop()
			ans.append([])
			ans[-1].append(curr)
			traverse(curr, float('inf'))
		ans.sort(key=lambda x: x[0])
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, p) = map(int, input().strip().split())
		a = []
		b = []
		d = []
		for i in range(p):
			(x, y, z) = map(int, input().strip().split())
			a.append(x)
			b.append(y)
			d.append(z)
		ob = Solution()
		ans = ob.solve(n, p, a, b, d)
		print(len(ans))
		for i in ans:
			print(str(i[0]) + ' ' + str(i[1]) + ' ' + str(i[2]))


import sys

class Solution:

	def solve(self, n, p, out, inc, dia):
		incoming_set = set()
		for ele in inc:
			incoming_set.add(ele)
		connections = {}
		for (i, ele) in enumerate(out):
			connections[ele] = (inc[i], dia[i])
		ans = []
		for ele in out:
			if ele not in incoming_set:
				(tap, dia) = self.get_min_diameter(ele, connections)
				ans.append([ele, tap, dia])
		return sorted(ans, key=lambda x: x[0])

	def get_min_diameter(self, tank, connections):
		pipe = sys.maxsize
		while tank in connections:
			(tank, d) = connections[tank]
			pipe = min(pipe, d)
		return (tank, pipe)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, p) = map(int, input().strip().split())
		a = []
		b = []
		d = []
		for i in range(p):
			(x, y, z) = map(int, input().strip().split())
			a.append(x)
			b.append(y)
			d.append(z)
		ob = Solution()
		ans = ob.solve(n, p, a, b, d)
		print(len(ans))
		for i in ans:
			print(str(i[0]) + ' ' + str(i[1]) + ' ' + str(i[2]))


from collections import defaultdict

class Solution:

	def solve(self, n, p, a, b, d):
		start = list(set(a) - set(b))
		graph = defaultdict(list)
		ans = []
		visited = [0] * (n + 1)
		for i in range(p):
			graph[a[i]].append([b[i], d[i]])

		def dfs(u, s, d):
			if len(graph[u]) == 0:
				ans.append([s, u, d])
				return
			for (neigh, d2) in graph[u]:
				dfs(neigh, s, min(d, d2))
		for s in start:
			dfs(s, s, float('inf'))
		return sorted(ans, key=lambda x: x[0])
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, p) = map(int, input().strip().split())
		a = []
		b = []
		d = []
		for i in range(p):
			(x, y, z) = map(int, input().strip().split())
			a.append(x)
			b.append(y)
			d.append(z)
		ob = Solution()
		ans = ob.solve(n, p, a, b, d)
		print(len(ans))
		for i in ans:
			print(str(i[0]) + ' ' + str(i[1]) + ' ' + str(i[2]))


class Solution:

	def solve(self, n, p, a, b, d):
		vis = [0] * (n + 1)
		out = [0] * (n + 1)
		adj = {}
		for i in range(len(a)):
			adj[a[i]] = [b[i], d[i]]
			out[b[i]] = 1

		def dfs(i):
			vis[i] = 1
			if adj[i][0] in adj:
				val = dfs(adj[i][0])
				return [val[0], min(val[1], adj[i][1])]
			else:
				return adj[i]
		ans = []
		for i in range(1, n + 1):
			if i in adj and out[i] == 0:
				if vis[i] != 1:
					val = dfs(i)
					ans.append([i, val[0], val[1]])
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(n, p) = map(int, input().strip().split())
		a = []
		b = []
		d = []
		for i in range(p):
			(x, y, z) = map(int, input().strip().split())
			a.append(x)
			b.append(y)
			d.append(z)
		ob = Solution()
		ans = ob.solve(n, p, a, b, d)
		print(len(ans))
		for i in ans:
			print(str(i[0]) + ' ' + str(i[1]) + ' ' + str(i[2]))


class Solution:

	def solve(self, n, p, a, b, d):
		i = 0
		while i < p:
			flag = 0
			for j in range(p):
				if i != j and a[j] != 0:
					if a[i] == b[j]:
						a[i] = a[j]
						a[j] = 0
						b[j] = 0
						flag = 1
						d[i] = min(d[i], d[j])
						break
					elif b[i] == a[j]:
						b[i] = b[j]
						a[j] = 0
						b[j] = 0
						flag = 1
						d[i] = min(d[i], d[j])
						break
			if flag == 0:
				i += 1
		rt = []
		for i in range(p):
			if a[i] != 0 and a[i] != b[i]:
				rt.append([a[i], b[i], d[i]])
		return sorted(rt)


class Solution:

	def solve(self, n, p, a, b, d):
		g = [[] for i in range(n + 1)]
		deg = [0 for i in range(n + 1)]
		for i in range(p):
			g[a[i]].append([b[i], d[i]])
			deg[a[i]] += 1
			deg[b[i]] -= 1
		vis = [False for i in range(n + 1)]
		ans = []
		for i in range(1, n + 1):
			if vis[i] == False and deg[i] == 1:
				tab = [0]
				dia = [999]
				self.dfs(g, vis, i, n, tab, dia)
				ans.append([i, tab[0], dia[0]])
		return ans

	def dfs(self, g, vis, node, n, tab, dia):
		vis[node] = True
		for curr in g[node]:
			(v, wt) = (curr[0], curr[1])
			dia[0] = min(dia[0], wt)
			if len(g[v]) == 0:
				tab[0] = v
				return
			if vis[v] == False:
				self.dfs(g, vis, v, n, tab, dia)


from collections import deque

class Solution:

	def solve(self, n, p, a, b, d):

		def dfs(node, adj, vis, wt, end):
			vis[node] = 1
			if not adj[node]:
				end[0] = node
			for ele in adj[node]:
				(child, weight) = ele
				if not vis[child]:
					wt[0] = min(wt[0], weight)
					dfs(child, adj, vis, wt, end)
		adj = [[] for _ in range(n + 1)]
		indeg = [0] * (n + 1)
		for i in range(p):
			adj[a[i]] += [[b[i], d[i]]]
			indeg[b[i]] += 1
		vis = [0] * (n + 1)
		arr = []
		for i in range(1, n + 1):
			if indeg[i] == 0:
				arr += [i]
		ans = []
		for ele in arr:
			if not vis[ele]:
				newwt = [10 ** 9]
				end = [None]
				dfs(ele, adj, vis, newwt, end)
				if ele != end[0]:
					ans += [[ele, end[0], newwt[0]]]
		return ans


class Solution:

	def solve(self, n, p, a, b, d):
		self.visited = [False] * (n + 1)
		connect_lines = []
		self.a = a
		self.b = b
		self.d = d
		min_dis = []
		res = []
		for i in range(1, n + 1):
			if i not in self.b:
				current_streak = []
				self.min_d = float('inf')
				self.DFS(i, current_streak)
				connect_lines.append(current_streak)
				min_dis.append(self.min_d)
		for i in range(len(connect_lines)):
			if min_dis[i] != float('inf') and len(connect_lines[i]) != 1:
				start = connect_lines[i][0]
				end = connect_lines[i][len(connect_lines[i]) - 1]
				dis = min_dis[i]
				curr_ans = []
				curr_ans.append(start)
				curr_ans.append(end)
				curr_ans.append(dis)
				res.append(curr_ans)
		return res

	def DFS(self, i, current_streak):
		self.visited[i] == True
		current_streak.append(i)
		for j in range(len(self.a)):
			if self.visited[j] == False and self.a[j] == i:
				if self.d[j] < self.min_d:
					self.min_d = self.d[j]
				self.DFS(self.b[j], current_streak)


class Solution:

	def solve(self, n, p, a, b, d):

		def dfs(w, ans, start, end, wt):
			if end[w] == 0:
				return w
			if wt[w] < ans[0]:
				ans[0] = wt[w]
			return dfs(end[w], ans, start, end, wt)
		start = [0 for i in range(n + 1)]
		end = [0 for i in range(n + 1)]
		wt = [0 for i in range(n + 1)]
		for i in range(p):
			start[b[i]] = a[i]
			end[a[i]] = b[i]
			wt[a[i]] = d[i]
		res = []
		for i in range(1, n + 1):
			if start[i] == 0 and end[i]:
				ans = [float('inf')]
				w = dfs(i, ans, start, end, wt)
				res += [[i, w, ans[0]]]
		return res


class Solution:

	def solve(self, n, p, a, b, d):
		ans = [[a[0], b[0], d[0]]]
		for i in range(1, len(a)):
			flag = 0
			pos = -1
			for j in range(len(ans)):
				if a[i] == ans[j][1]:
					flag += 1
					if flag == 2:
						ans[pos][0] = ans[j][0]
						ans[pos][2] = min(ans[j][2], ans[pos][2])
						ans.pop(j)
						break
					pos = j
					ans[j][1] = b[i]
					ans[j][2] = min(ans[j][2], d[i])
				if b[i] == ans[j][0]:
					flag += 1
					if flag == 2:
						ans[pos][1] = ans[j][1]
						ans[pos][2] = min(ans[j][2], ans[pos][2])
						ans.pop(j)
						break
					pos = j
					ans[j][0] = a[i]
					ans[j][2] = min(ans[j][2], d[i])
			if flag == 0:
				ans.append([a[i], b[i], d[i]])
		return sorted(ans)


class Solution:
	x = 11111111

	def dfs(self, ind, out, d):
		global x
		if out[ind] == 0:
			return ind
		if d[ind] < x:
			x = d[ind]
		return self.dfs(out[ind], out, d)

	def solve(self, n, p, a, b, c):
		global x
		inp = [0 for i in range(n + 1)]
		out = [0 for i in range(n + 1)]
		d = [0 for i in range(n + 1)]
		ans = []
		for i in range(p):
			t = a[i]
			y = b[i]
			u = c[i]
			out[t] = y
			inp[y] = t
			d[t] = u
		for i in range(1, n + 1):
			if inp[i] == 0 and out[i]:
				x = 12546357
				en = self.dfs(i, out, d)
				ans.append([i, en, x])
		return ans


import queue
from collections import defaultdict

class Solution:

	def solve(self, n, p, a, b, d):
		ans = []
		rem = set(a) - set(b)
		r = sorted(rem)
		adj = defaultdict(list)
		(visited, val1, val2) = ({}, {}, {})
		for i in range(p):
			adj[a[i]].append([b[i], 2])
			val2[b[i]] = d[i]
			val1[a[i]] = d[i]
			visited[a[i]] = False
			visited[b[i]] = False
		q = queue.deque()
		for i in r:
			q.append([i, 1])
			last = i
			radi = val1[i]
			while q:
				u = q.popleft()
				last = u[0]
				if u[1] == 1:
					radi = min(radi, val1[last])
				else:
					radi = min(radi, val2[last])
				for v in adj[u[0]]:
					if not visited[v[0]]:
						q.append([v[0], v[1]])
			ans.append([i, last, radi])
		return ans


class Solution:

	def solve(self, n, p, a, b, d):
		adj = dict()
		check = set(b)
		for i in range(len(d)):
			adj[a[i]] = (b[i], d[i])

		def dfs(v):
			nonlocal adj, path, visited
			path += [v]
			visited.add(v)
			if v in adj:
				dfs(adj[v][0])
		ans = []
		for i in range(1, n + 1):
			visited = set()
			if i not in check and i not in visited and (i in adj):
				path = []
				dfs(i)
				fin = 10 ** 10
				for i in path[:-1]:
					fin = min(fin, adj[i][1])
				x = [path[0], path[-1], fin]
				ans.append(x)
		return ans


from functools import cmp_to_key

def compare(x, y):
	return x[0] - y[0]

class Solution:

	def Check(self, mp, b, j):
		comp = False
		try:
			comp = mp[b[j]]
		except:
			comp = None
		return comp

	def solve(self, n, p, a, b, d):
		mp = {}
		sett = set(b)
		for i in range(p):
			mp[a[i]] = i
		for j in range(p):
			if a[j] in sett:
				continue
			comp = self.Check(mp, b, j)
			while comp != None:
				d[j] = min(d[j], d[comp])
				b[j] = b[comp]
				comp = self.Check(mp, b, j)
		ans = []
		for k in range(p):
			if a[k] not in sett:
				ans.append([a[k], b[k], d[k]])
		return sorted(ans, key=cmp_to_key(compare))


class Solution:

	def solve(self, n, p, a, b, d):
		pipe = []
		tank = []
		for i in b:
			if i not in a:
				pipe.append(i)
		for j in a:
			if j not in b:
				tank.append(j)
		tank.sort()
		hashtable = {}
		for i in range(len(a)):
			hashtable[a[i]] = [b[i], d[i]]
		res = []
		ans = []
		for i in tank:
			ans.append(i)
			temp = hashtable[i]
			min_dia = temp[1]
			while temp[0] not in pipe:
				temp = hashtable[temp[0]]
				min_dia = min(min_dia, temp[1])
			ans.append(temp[0])
			ans.append(min_dia)
			res.append(ans)
			ans = []
		return res