Given a weighted, undirected and connected graph of V vertices and E edges. The task is to find the sum of weights of the edges of the Minimum Spanning Tree.
 
Example 1:
Input:
3 3
0 1 5
1 2 3
0 2 1
Output:
4
Explanation:
The Spanning Tree resulting in a weight
of 4 is shown above.
Example 2:
Input:
2 1
0 1 5
Output:
5
Explanation:
Only one Spanning Tree is possible
which has a weight of 5.
 
Your task:
Since this is a functional problem you don't have to worry about input, you just have to complete the function spanningTree() which takes a number of vertices V and an adjacency matrix adj as input parameters and returns an integer denoting the sum of weights of the edges of the Minimum Spanning Tree. Here adj[i] contains a list of three integers, first integer and second integer denotes that there is an edge between adj[i][0] and adj[i][1] and the third integer denotes the weight of that edge i.e. adj[i][2]
In other words, adj[i][j] is of form  { u, v, wt }. So, this denotes that there is an edge between u and v with an edge weight equal to wt.
 
Expected Time Complexity: O(ElogV).
Expected Auxiliary Space: O(V^{2}).
 
Constraints:
2  ≤  V ≤  1000
V-1 ≤  E  ≤  (V*(V-1))/2
1  ≤  w  ≤  1000
The graph is connected and doesn't contain self-loops & multiple edges.

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph algorithms

Data structures

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    

    #Function to find sum of weights of edges of the Minimum Spanning Tree.

    def spanningTree(self, V, adj):

        #code here

Solutions:
import heapq

class Solution:

	def spanningTree(self, V, adj):
		visited = [False] * V
		pq = []
		ans = 0
		heapq.heappush(pq, (0, 0))
		while pq:
			(w, u) = heapq.heappop(pq)
			if visited[u]:
				continue
			ans += w
			visited[u] = True
			for (v, w) in adj[u]:
				if not visited[v]:
					heapq.heappush(pq, (w, v))
		return ans


import heapq

class Solution:

	def findparent(self, node, parent):
		if parent[node] == node:
			return node
		parent[node] = self.findparent(parent[node], parent)
		return parent[node]

	def unite(self, node, edge, a, b, parent):
		parent[max(a, b)] = min(a, b)

	def spanningTree(self, V, adj):
		parent = [i for i in range(V)]
		size = [1 for i in range(V)]
		edges = []
		sum1 = 0
		for i in range(V):
			node = i
			for (edge, wei) in adj[node]:
				heapq.heappush(edges, [wei, node, edge])
		while len(edges):
			(cost, node, edge) = heapq.heappop(edges)
			a = self.findparent(node, parent)
			b = self.findparent(edge, parent)
			if a == b:
				continue
			sum1 += cost
			self.unite(node, edge, a, b, parent)
		return sum1


import heapq

class Solution:

	def findparent(self, node, parent):
		if parent[node] == node:
			return node
		parent[node] = self.findparent(parent[node], parent)
		return parent[node]

	def unite(self, node1, node2, size, parent, e1, e2):
		parent[max(e1, e2)] = min(e1, e2)

	def spanningTree(self, V, adj):
		parent = [i for i in range(V)]
		size = [1 for i in range(V)]
		edges = []
		sum1 = 0
		for i in range(V):
			node = i
			for (edge, wei) in adj[node]:
				heapq.heappush(edges, [wei, node, edge])
		while len(edges) > 0:
			(cost, u, v) = heapq.heappop(edges)
			e1 = self.findparent(u, parent)
			e2 = self.findparent(v, parent)
			if e1 == e2:
				continue
			sum1 += cost
			self.unite(u, v, size, parent, e1, e2)
		return sum1


class Solution:

	def spanningTree(self, v, graph):
		key = [999999999] * v
		key[0] = 0
		mst = [False] * v
		res = 0
		for count in range(v):
			u = -1
			for i in range(v):
				if mst[i] == False and (u == -1 or key[i] < key[u]):
					u = i
			res += key[u]
			mst[u] = True
			for (j, wt) in graph[u]:
				if wt != 0:
					key[j] = min(key[j], wt)
		return res


import heapq

class Solution:

	def spanningTree(self, V, adj):
		pq = []
		vis = [0] * V
		sums = 0
		heapq.heappush(pq, [0, 0])
		while pq:
			(wt, node) = heapq.heappop(pq)
			if vis[node]:
				continue
			vis[node] = 1
			sums += wt
			for (adjNode, edWt) in adj[node]:
				heapq.heappush(pq, [edWt, adjNode])
		return sums


class Solution:

	def spanningTree(self, V, adj):
		return mst(adj)
from queue import PriorityQueue

def mst(G):
	n = len(G)
	visited = [False] * n
	mst_array = []
	pq = PriorityQueue()
	u = 0
	visited[u] = True
	for i in range(n - 1):
		for (v, w) in G[u]:
			if not visited[v]:
				pq.put((w, u, v))
		(w, u, v) = pq.get()
		while visited[v]:
			(w, u, v) = pq.get()
		visited[v] = True
		mst_array.append((u, v, w))
		u = v
	s = 0
	for (u, v, w) in mst_array:
		s += w
	return s


import heapq

class Solution:

	def spanningTree(self, V, adj):
		li = []
		heapq.heappush(li, [0, 0])
		vis = [False for i in range(V)]
		sum1 = 0
		while len(li) > 0:
			(dist, node) = heapq.heappop(li)
			if vis[node] == 1:
				continue
			vis[node] = 1
			sum1 += dist
			for (edge, cost) in adj[node]:
				heapq.heappush(li, [cost, edge])
		return sum1


class Solution:

	def getminvertex(self, visited, weight):
		minwt = sys.maxsize
		for v in range(V):
			if visited[v] == False and weight[v] < minwt:
				minwt = weight[v]
				min_index = v
		return min_index

	def spanningTree(self, V, adj):
		parent = [-1 for i in range(V)]
		visited = [False for i in range(V)]
		weight = [sys.maxsize for i in range(V)]
		weight[0] = 0
		mincost = 0
		for i in range(V):
			minvertex = self.getminvertex(visited, weight)
			visited[minvertex] = True
			mincost += weight[minvertex]
			for (neighbour_vertex, wt) in adj[minvertex]:
				if visited[neighbour_vertex] == False and weight[neighbour_vertex] > wt:
					weight[neighbour_vertex] = wt
					parent[neighbour_vertex] = minvertex
		return mincost


import heapq

class Solution:

	def spanningTree(self, V, graph):

		def find(x, parent):
			if parent[x] == x:
				return x
			tmp = find(parent[x], parent)
			parent[x] = tmp
			return tmp

		def union(x, y, parent, rank):
			lx = find(x, parent)
			ly = find(y, parent)
			if lx != ly:
				if rank[lx] > rank[ly]:
					parent[ly] = lx
				elif rank[ly] > rank[lx]:
					parent[lx] = ly
				else:
					parent[lx] = ly
					rank[ly] += 1
				return True
			else:
				return False
		parent = [i for i in range(V)]
		rank = [0 for i in range(V)]
		arr = []
		for node in range(V):
			for neighbor in graph[node]:
				arr.append([node, neighbor[0], neighbor[1]])
		arr.sort(key=lambda x: x[2])
		ans = 0
		for edge in arr:
			res = union(edge[0], edge[1], parent, rank)
			if res:
				ans += edge[2]
		return ans


class edge:

	def __init__(self, v1, v2, wt):
		self.v1 = v1
		self.v2 = v2
		self.wt = wt

class Solution:

	def get_parent(self, i, parent):
		if parent[i] != i:
			parent[i] = self.get_parent(parent[i], parent)
		return parent[i]

	def union(self, x, y, parent, rank):
		if rank[x] > rank[y]:
			parent[y] = x
		elif rank[y] > rank[x]:
			parent[x] = y
		else:
			parent[y] = x
			rank[x] += 1

	def spanningTree(self, V, adj):
		ans = []
		li = []
		parent = [i for i in range(V)]
		rank = [0 for i in range(V)]
		for v1 in range(V):
			for (v2, wt) in adj[v1]:
				li.append(edge(v1, v2, wt))
		li = sorted(li, key=lambda edge: edge.wt)
		edges = 0
		i = 0
		while edges < V - 1:
			current_edge = li[i]
			p1 = self.get_parent(current_edge.v1, parent)
			p2 = self.get_parent(current_edge.v2, parent)
			if p1 != p2:
				ans.append(current_edge)
				self.union(p1, p2, parent, rank)
				edges += 1
			i += 1
		mincost = 0
		for i in ans:
			mincost += i.wt
		return mincost


from collections import defaultdict
import heapq

class Solution:

	def spanningTree(self, V, adj):
		parent = [x for x in range(V)]
		rank = [0 for x in range(V)]

		def Find(a):
			if parent[a] == a:
				return a
			parent[a] = Find(parent[a])
			return parent[a]

		def Union(a, b):
			(a, b) = (Find(a), Find(b))
			if rank[a] < rank[b]:
				parent[a] = parent[b]
				rank[b] += rank[a]
			else:
				parent[b] = parent[a]
				rank[a] += rank[b]
		g = []
		for x in range(V):
			for (i, j) in adj[x]:
				g.append([x, i, j])
		g.sort(key=lambda x: x[2])
		vi = 0
		ans = []
		while vi < V - 1:
			for (u, v, w) in g:
				if vi >= V - 1:
					break
				if Find(u) != Find(v):
					ans.append([u, v, w])
					vi += 1
					Union(Find(u), Find(v))
		f = 0
		for (x, y, z) in ans:
			f += z
		return f


from collections import defaultdict
import heapq

class Solution:

	def spanningTree(self, V, adj):
		g = defaultdict(set)
		for x in range(V):
			for (node, dist) in adj[x]:
				g[x].add((dist, node))
				g[node].add((dist, x))
		h = []
		heapq.heapify(h)
		heapq.heappush(h, (0, 0))
		v = set()
		ans = 0
		while len(v) < V:
			(dist, node) = heapq.heappop(h)
			if node in v:
				continue
			v.add(node)
			ans += dist
			for (x, y) in g[node]:
				if y not in v:
					heapq.heappush(h, (x, y))
		return ans


from queue import PriorityQueue

class Solution:

	def spanningTree(self, V, adj):
		s = 0
		q = PriorityQueue()
		q.put((0, 0))
		visited = set()
		while not q.empty():
			(dist, node) = q.get()
			if node in visited:
				continue
			s += dist
			visited.add(node)
			for (adjNode, edW) in adj[node]:
				if adjNode not in visited:
					q.put((edW, adjNode))
		return s


import heapq
from collections import defaultdict

class Solution:

	def spanningTree(self, V, adj):
		vis = set()
		heap = []
		mst = []
		sum = 0
		adjLi = defaultdict(list)
		heapq.heappush(heap, [0, 0, -1])
		while len(heap) != 0:
			p = heapq.heappop(heap)
			wt = p[0]
			node = p[1]
			parent = p[2]
			if node not in vis:
				vis.add(node)
				mst.append((node, parent))
				sum += wt
				for n in adj[node]:
					nbr = n[0]
					w = n[1]
					if nbr not in vis:
						heapq.heappush(heap, [w, nbr, node])
		return sum


import heapq

class Solution:

	def spanningTree(self, V, adj):
		heap = []
		visited = [False for i in range(V)]
		heapq.heappush(heap, (0, 0))
		final_wt = 0
		while len(heap) > 0:
			current_val = heapq.heappop(heap)
			current_node = current_val[1]
			if not visited[current_node]:
				final_wt = current_val[0] + final_wt
				visited[current_node] = True
				neigh = adj[current_node]
				for n in neigh:
					heapq.heappush(heap, [n[1], n[0]])
		return final_wt


import heapq

class DisjointSet:

	def __init__(self, V):
		self.rank = [0] * (V + 1)
		self.parent = [i for i in range(V + 1)]
		self.size = [1] * (V + 1)

	def findUltimateParent(self, node):
		if self.parent[node] == node:
			return node
		self.parent[node] = self.findUltimateParent(self.parent[node])
		return self.parent[node]

	def unionByRank(self, u, v):
		ultimateParentU = self.findUltimateParent(u)
		ultimateParentV = self.findUltimateParent(v)
		if ultimateParentU == ultimateParentV:
			return
		if self.rank[ultimateParentV] < self.rank[ultimateParentU]:
			self.parent[ultimateParentV] = ultimateParentU
		elif self.rank[ultimateParentU] < self.rank[ultimateParentV]:
			self.parent[ultimateParentU] = ultimateParentV
		else:
			self.parent[ultimateParentU] = ultimateParentV
			self.rank[ultimateParentV] += 1

	def unioBySize(self, u, v):
		ultimateParentU = self.findUltimateParent(u)
		ultimateParentV = self.findUltimateParent(v)
		if ultimateParentU == ultimateParentV:
			return
		if self.size[ultimateParentV] < self.size[ultimateParentU]:
			self.parent[ultimateParentV] = ultimateParentU
			self.size[ultimateParentU] += self.size[ultimateParentV]
		else:
			self.parent[ultimateParentU] = ultimateParentV
			self.size[ultimateParentV] += self.size[ultimateParentU]

class Solution:

	def spanningTree(self, V, adj):
		edges = []
		for i in range(V):
			for it in adj[i]:
				adjNode = it[0]
				weight = it[1]
				node = i
				edges.append([weight, node, adjNode])
		ds = DisjointSet(V)
		edges.sort(key=lambda x: x[0])
		sumMSTWt = 0
		for it in edges:
			weight = it[0]
			node = it[1]
			adjNode = it[2]
			if ds.findUltimateParent(node) != ds.findUltimateParent(adjNode):
				sumMSTWt += weight
				ds.unionByRank(node, adjNode)
		return sumMSTWt


import heapq

class Solution:

	def spanningTree(self, V, adj):
		(queue, res) = ([], 0)
		visited = set()
		heapq.heappush(queue, (0, 0))
		while queue:
			(curr_dist, node) = heapq.heappop(queue)
			if node not in visited:
				visited.add(node)
				res += curr_dist
				for (nei, dist) in adj[node]:
					if nei not in visited:
						heapq.heappush(queue, (dist, nei))
		return res


class DisjointSet:
	(rank, parent, size) = ([], [], [])

	def __init__(self, n):
		self.rank = [0] * (n + 1)
		self.parent = [None] * (n + 1)
		self.size = [None] * (n + 1)
		for i in range(n + 1):
			self.parent[i] = i
			self.size[i] = 1

	def findUPar(self, node) -> int:
		if node == self.parent[node]:
			return node
		self.parent[node] = self.findUPar(self.parent[node])
		return self.parent[node]

	def unionByRank(self, u, v):
		(ulp_u, ulp_v) = (self.findUPar(u), self.findUPar(v))
		if ulp_u == ulp_v:
			return
		if self.rank[ulp_u] < self.rank[ulp_v]:
			self.parent[ulp_u] = ulp_v
		elif self.rank[ulp_v] < self.rank[ulp_u]:
			self.parent[ulp_v] = ulp_u
		else:
			self.parent[ulp_v] = ulp_u
			self.rank[ulp_u] += 1

	def unionBySize(self, u, v):
		(ulp_u, ulp_v) = (self.findUPar(u), self.findUPar(v))
		if ulp_u == ulp_v:
			return
		if self.size[ulp_u] < self.size[ulp_v]:
			self.parent[ulp_u] = self.parent[ulp_v]
			self.size[ulp_v] += self.size[ulp_u]
		else:
			self.parent[ulp_v] = ulp_u
			self.size[ulp_u] += self.size[ulp_v]

class Solution:

	def spanningTree(self, V, adj):
		edges = []
		for i in range(V):
			for it in adj[i]:
				adjNode = it[0]
				wt = it[1]
				node = i
				edges.append((wt, (node, adjNode)))
		ds = DisjointSet(V)
		edges.sort()
		mstWt = 0
		for it in edges:
			(wt, u, v) = (it[0], it[1][0], it[1][1])
			if ds.findUPar(u) != ds.findUPar(v):
				mstWt += wt
				ds.unionBySize(u, v)
		return mstWt


from sys import maxsize
import heapq

class Solution:

	def spanningTree(self, V, adj):
		mst = [False] * V
		dist = [maxsize] * V
		dist[0] = 0
		min_heap = []
		heapq.heappush(min_heap, (0, 0))
		while min_heap:
			(d, node) = heapq.heappop(min_heap)
			mst[node] = True
			for (nbr, wt) in adj[node]:
				if not mst[nbr] and wt < dist[nbr]:
					dist[nbr] = wt
					heapq.heappush(min_heap, (dist[nbr], nbr))
		for i in range(V):
			if dist[i] == maxsize:
				dist[i] = 0
		return sum(dist)


import heapq

class Solution:

	def spanningTree(self, V, adj):
		(pq, vis) = ([], [0] * V)
		heapq.heappush(pq, (0, 0))
		sum = 0
		while pq:
			wt = pq[0][0]
			node = pq[0][1]
			heapq.heappop(pq)
			if vis[node] == 1:
				continue
			vis[node] = 1
			sum += wt
			for i in range(len(adj[node])):
				edW = adj[node][i][1]
				adjNode = adj[node][i][0]
				if vis[adjNode] == 0:
					heapq.heappush(pq, (edW, adjNode))
		return sum


import heapq

class Solution:

	def spanningTree(self, V, adj):
		vis = [0] * V
		pq = [(0, 0)]
		heapq.heapify(pq)
		summst = 0
		while len(pq) != 0:
			elem = heapq.heappop(pq)
			wt = elem[0]
			node = elem[1]
			if not vis[node]:
				vis[node] = 1
				summst += wt
				for it in adj[node]:
					adjNode = it[0]
					adjWt = it[1]
					heapq.heappush(pq, (adjWt, adjNode))
		return summst


class DSU:

	def __init__(self, n):
		self.parent = [i for i in range(n + 1)]
		self.rank = [0] * (n + 1)
		self.size = [1] * (n + 1)

	def findUltPrnt(self, u):
		if self.parent[u] == u:
			return u
		self.parent[u] = self.findUltPrnt(self.parent[u])
		return self.parent[u]

	def unionByRank(self, u, v):
		(ult_u, ult_v) = (self.findUltPrnt(u), self.findUltPrnt(v))
		if ult_u == ult_v:
			return False
		if self.rank[ult_u] < self.rank[ult_v]:
			self.parent[ult_u] = ult_v
		else:
			self.parent[ult_v] = ult_u
			if self.rank[ult_u] == self.rank[ult_v]:
				self.rank[ult_u] += 1
		return True

	def unionBySize(self, u, v):
		(ult_u, ult_v) = (self.findUltPrnt(u), self.findUltPrnt(v))
		if ult_u == ult_v:
			return False
		if self.size[ult_u] < self.size[ult_v]:
			self.parent[ult_u] = ult_v
			self.size[ult_v] += self.size[ult_u]
		else:
			self.parent[ult_v] = ult_u
			self.parent[ult_u] += self.size[ult_v]
		return True
import heapq

class Solution:

	def spanningTree(self, V, adj):
		(res, edges) = (0, [])
		dsu = DSU(V)
		for node in range(V):
			for (adjNode, adjWt) in adj[node]:
				heapq.heappush(edges, (adjWt, node, adjNode))
		while edges:
			(wt, u, v) = heapq.heappop(edges)
			if dsu.unionByRank(u, v):
				res += wt
		return res


import heapq

class Solution:

	def spanningTree(self, V, graph):
		pq = [(0, 0)]
		visited = set()
		heapq.heapify(pq)
		ans = 0
		while pq:
			(dist, node) = heapq.heappop(pq)
			if node in visited:
				continue
			ans += dist
			visited.add(node)
			if len(visited) == V:
				return ans
			for neighbor in graph[node]:
				if neighbor[0] not in visited:
					heapq.heappush(pq, (neighbor[1], neighbor[0]))


class Solution:

	def spanningTree(self, V, adj):
		from collections import defaultdict
		from heapq import heappop, heappush
		adj_list = defaultdict(list)
		for (u, nmb) in enumerate(adj):
			for (v, w) in nmb:
				adj_list[u].append((v, w))
		distance = [float('inf')] * V
		parent = {}
		h = []

		def add(u, d, p):
			distance[u] = d
			parent[u] = p
			for (v, w) in adj_list[u]:
				if v not in parent:
					heappush(h, (w, u, v))
		add(0, 0, None)
		while h:
			(w, u, v) = heappop(h)
			if v not in parent:
				add(v, w, u)
		return sum(distance)


from heapq import heapify, heappush, heappop

class Solution:

	def spanningTree(self, V, adj):
		parent = [i for i in range(V)]
		rank = [0 for i in range(V)]

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

		def union(x, y):
			xset = find(x)
			yset = find(y)
			if xset == yset:
				return
			if rank[xset] > rank[yset]:
				parent[yset] = xset
			elif rank[yset] > rank[xset]:
				parent[xset] = yset
			else:
				parent[yset] = xset
				rank[xset] += 1
		l = []
		for i in range(len(adj)):
			for j in adj[i]:
				l.append([j[1], i, j[0]])
		l.sort()
		ans = 0
		for i in l:
			w = i[0]
			x = i[1]
			y = i[2]
			if find(x) != find(y):
				union(x, y)
				ans += w
		return ans


import heapq

class Solution:

	def spanningTree(self, V, adj):
		heap = []
		for (target, price) in adj[0]:
			heapq.heappush(heap, (price, target))
		visited = set([0])
		output = 0
		while heap:
			(cost, node) = heapq.heappop(heap)
			if node in visited:
				continue
			visited.add(node)
			output += cost
			for (target, price) in adj[node]:
				if not target in visited:
					heapq.heappush(heap, (price, target))
		return output


class Solution:

	def spanningTree(self, V, adj):
		import sys
		sys.setrecursionlimit(10 ** 6)
		arr = [i for i in range(V)]
		edges = []
		for (u, nbrs) in enumerate(adj):
			for (v, w) in nbrs:
				edges.append((u, v, w))
		edges.sort(key=lambda e: e[2])

		def find(i):
			if arr[i] != i:
				arr[i] = find(arr[i])
			return arr[i]
		ans = 0
		for (u, v, w) in edges:
			(ru, rv) = (find(u), find(v))
			if ru != rv:
				arr[ru] = rv
				ans += w
		return ans


from heapq import *

class Solution:

	def spanningTree(self, V, adj):
		minheap = []
		heappush(minheap, (0, 0))
		res = 0
		visited = [False for i in range(V)]
		while minheap:
			(wt, node) = heappop(minheap)
			if visited[node] == True:
				continue
			visited[node] = True
			res += wt
			for edge in adj[node]:
				nextNode = edge[0]
				nextWt = edge[1]
				if visited[nextNode]:
					continue
				heappush(minheap, (nextWt, nextNode))
		return res


import heapq

class Solution:

	def spanningTree(self, V, adj):
		heap = [(0, 0)]
		visited = [False] * V
		res = 0
		while heap:
			(wt, node) = heapq.heappop(heap)
			if not visited[node]:
				visited[node] = True
				res += wt
				for (adjNode, adjWt) in adj[node]:
					if not visited[adjNode]:
						heapq.heappush(heap, (adjWt, adjNode))
		return res


class Edge:

	def __init__(self, u, v, w):
		self.u = u
		self.v = v
		self.w = w

	def __hash__(self):
		if self.u < self.v:
			return str(self.u) + '--' + str(self.v)
		else:
			return str(self.v) + '--' + str(self.u)

	def __repr__(self):
		return str(self.u) + '<-->' + str(self.v) + '=' + str(self.w)

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

class Solution:

	def find_parent(self, u):
		p_u = self.parent[u]
		if p_u == u:
			return p_u
		else:
			self.parent[u] = self.find_parent(p_u)
			return self.parent[u]

	def union(self, p_u, p_v):
		(r_u, r_v) = (self.rank[p_u], self.rank[p_v])
		if r_u < r_v:
			self.parent[p_u] = p_v
		elif r_u > r_v:
			self.parent[p_v] = p_u
		else:
			self.rank[p_u] += 1
			self.parent[p_v] = p_u

	def spanningTree(self, V, adj):
		all_edges = list()
		self.parent = [i for i in range(V)]
		self.rank = [0 for i in range(V)]
		for u in range(V):
			for (v, w) in adj[u]:
				if u < v:
					all_edges.append(Edge(u, v, w))
		mst = []
		for edge in sorted(all_edges):
			p_u = self.find_parent(edge.u)
			p_v = self.find_parent(edge.v)
			if p_u == p_v:
				continue
			else:
				mst.append(edge)
				self.union(p_u, p_v)
		sum = 0
		for edge in mst:
			sum += edge.w
		return sum


import sys

class Solution:

	def spanningTree(self, V, adj):
		sys.setrecursionlimit(10 ** 6)
		arr = [i for i in range(V)]
		edges = []
		for (u, nbrs) in enumerate(adj):
			for (v, w) in nbrs:
				edges.append((u, v, w))
		edges.sort(key=lambda e: e[2])

		def find(i):
			if arr[i] != i:
				arr[i] = find(arr[i])
			return arr[i]
		ans = 0
		for (u, v, w) in edges:
			(ru, rv) = (find(u), find(v))
			if ru != rv:
				arr[ru] = rv
				ans += w
		return ans

class DJS:

	def __init__(self, n):
		self.par = [i for i in range(n + 1)]
		self.rank = [0] * (n + 1)
		self.size = [1] * (n + 1)

	def find(self, u):
		if u != self.par[u]:
			self.par[u] = self.find(self.par[u])
			return self.par[u]
		return u

	def union(self, u, v):
		pu = self.find(u)
		pv = self.find(v)
		if pu == pv:
			return
		if self.rank[pu] < self.rank[pv]:
			self.par[pu] = pv
		else:
			self.par[pv] = pu
			if self.rank[pu] == self.rank[pv]:
				self.rank[pu] += 1

	def union_by_size(self, u, v):
		pu = self.find(u)
		pv = self.find(v)
		if pu == pv:
			return
		if self.size[pu] < self.size[pv]:
			self.par[pu] = pv
			self.size[pv] += self.size[pu]
		else:
			self.par[pv] = pu
			self.size[pu] += self.size[pv]


from queue import PriorityQueue

class Solution:

	def spanningTree(self, V, adj):
		q = PriorityQueue()
		vis = [0] * V
		q.put((0, 0))
		sum = 0
		while not q.empty():
			item = q.get()
			w = item[0]
			node = item[1]
			if vis[node] == 1:
				continue
			vis[node] = 1
			sum += w
			for i in adj[node]:
				adjnode = i[0]
				edw = i[1]
				if vis[adjnode] == 0:
					q.put((edw, adjnode))
		return sum


class Solution:

	def spanningTree(self, V, adj):
		vis = [0 for i in range(V)]
		pq = []
		ans = 0
		import heapq
		heapq.heappush(pq, [0, 0, -1])
		while len(pq) != 0:
			(wt, cn, pn) = heapq.heappop(pq)
			if vis[cn] == 0:
				ans += wt
				vis[cn] = 1
				for i in adj[cn]:
					(nn, nwt) = i
					heapq.heappush(pq, [nwt, nn, cn])
		return ans


import heapq
import sys

class Solution:

	def spanningTree(self, V, adj):
		pq = [[0, 0]]
		visited = [0] * V
		ans = 0
		while len(pq) != 0:
			(wt, node) = heapq.heappop(pq)
			if visited[node] == 1:
				continue
			ans += wt
			visited[node] = 1
			for (neb, edge) in adj[node]:
				if visited[neb] == 0:
					heapq.heappush(pq, [edge, neb])
		return ans


from heapq import heapify, heappush, heappop

class Solution:

	def spanningTree(self, V, adj):
		vis = [0] * V
		queue = [[0, 0]]
		heapify(queue)
		s = 0
		while queue:
			(dist, node) = heappop(queue)
			if vis[node]:
				continue
			vis[node] = 1
			s += dist
			for i in adj[node]:
				if not vis[i[0]]:
					heappush(queue, [i[1], i[0]])
		return s


class Solution:

	def parentrec(self, i, parent):
		if parent[i] == i:
			return i
		return self.parentrec(parent[i], parent)

	def spanningTree(self, V, adj):
		parent = []
		edge = []
		s = set()
		for i in range(V):
			parent.append(i)
		for i in range(len(adj)):
			for j in adj[i]:
				if (i, j[0]) not in s or (j[0], i) not in s:
					edge.append([i, j[0], j[1]])
					s.add((i, j[0]))
					s.add((j[0], i))
		ss = 0
		i = 0
		summ = 0
		edge.sort(key=lambda a: a[2])
		while ss < V - 1:
			x = edge[i][0]
			y = edge[i][1]
			px = self.parentrec(x, parent)
			py = self.parentrec(y, parent)
			if px != py:
				summ = summ + edge[i][2]
				parent[py] = px
				ss += 1
			i += 1
		return summ


class Solution:

	def spanningTree(self, V, adj):

		class Node:

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

		def findSet(x):
			if x.parent != x:
				x.parent = findSet(x.parent)
			return x.parent

		def findUnion(x, y):
			x = findSet(x)
			y = findSet(y)
			if x.rank > y.rank:
				y.parent = x
			else:
				x.parent = y
				if x.rank == y.rank:
					y.rank += 1

		def Kruskal(E, n):
			A = []
			s = 0
			V = [Node(i) for i in range(n)]
			E.sort(key=lambda x: x[2])
			for e in E:
				(u, v, w) = e
				if findSet(V[u]) != findSet(V[v]):
					findUnion(V[u], V[v])
					A += [e]
					s += w
			return s
		E = []
		for i in range(len(adj)):
			for j in range(len(adj[i])):
				E.append((i, adj[i][j][0], adj[i][j][1]))
		return Kruskal(E, V)


from heapq import heappush, heappop
from collections import defaultdict

class UnionFind:

	def __init__(self, n):
		self.root = list(range(n))
		self.rank = [1] * n

	def find(self, x):
		if x == self.root[x]:
			return x
		self.root[x] = self.find(self.root[x])
		return self.root[x]

	def union(self, x, y):
		rootx = self.root[x]
		rooty = self.root[y]
		if rootx != rooty:
			if self.rank[rootx] > self.rank[rooty]:
				self.root[rooty] = rootx
			elif self.rank[rootx] < self.rank[rooty]:
				self.root[rootx] = rooty
			else:
				self.root[rooty] = rootx
				self.rank[rootx] += 1

class Solution:

	def spanningTree(self, V, adj):
		UF = UnionFind(V)
		summ = 0
		l = []
		for i in range(V):
			for j in adj[i]:
				l.append((j[1], i, j[0]))
		l.sort()
		for each in l:
			if UF.find(each[1]) != UF.find(each[2]):
				summ += each[0]
				UF.union(each[1], each[2])
		return summ


class Solution:

	def spanningTree(self, V, adj):
		from heapq import heappush, heappop
		from collections import defaultdict
		arr = [i for i in range(V)]
		g = defaultdict(list)
		for (u, nbrs) in enumerate(adj):
			for (v, w) in nbrs:
				g[u].append((v, w))
		distance = [float('inf')] * V
		parent = {}
		h = []

		def add(u, d, p):
			distance[u] = d
			parent[u] = p
			for (v, w) in g[u]:
				if v not in parent:
					heappush(h, (w, u, v))
		add(0, 0, None)
		while h:
			(w, _, v) = heappop(h)
			if v not in parent:
				add(v, w, u)
		return sum(distance)


class DisjointSet:

	def __init__(self, V):
		self.rank = [0 for _ in range(V)]
		self.size = [1 for _ in range(V)]
		self.par = [i for i in range(V)]

	def findPar(self, node):
		if node == self.par[node]:
			return node
		self.par[node] = self.findPar(self.par[node])
		return self.par[node]

	def unionByRank(self, u, v):
		ulp_u = self.findPar(u)
		ulp_v = self.findPar(v)
		if ulp_v == ulp_u:
			return
		if self.rank[ulp_u] < self.rank[ulp_v]:
			self.par[ulp_u] = ulp_v
		elif self.rank[ulp_u] > self.rank[ulp_v]:
			self.par[ulp_v] = ulp_u
		else:
			self.par[ulp_v] = ulp_u
			self.rank[ulp_u] += 1

	def unionBySize(self, u, v):
		ulp_u = self.findPar(u)
		ulp_v = self.findPar(v)
		if ulp_v == ulp_u:
			return
		if self.size[ulp_u] < self.size[ulp_v]:
			self.par[ulp_u] = ulp_v
			self.size[ulp_v] += self.size[ulp_u]
		else:
			self.par[ulp_v] = ulp_u
			self.size[ulp_u] += self.size[ulp_v]

class Solution:

	def spanningTree(self, V, adj):
		edges = list()
		for node in range(V):
			for (adjNode, wt) in adj[node]:
				edges.append((wt, node, adjNode))
		ob = DisjointSet(V)
		edges.sort()
		res = 0
		for (wt, node, adjNode) in edges:
			if ob.findPar(node) != ob.findPar(adjNode):
				res += wt
				ob.unionByRank(node, adjNode)
		return res


class Solution:

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

	def union(parent, rank, x, y):
		xroot = Solution.find(parent, x)
		yroot = Solution.find(parent, y)
		if rank[xroot] < rank[yroot]:
			parent[xroot] = yroot
		elif rank[xroot] > rank[yroot]:
			parent[yroot] = xroot
		else:
			parent[yroot] = xroot
			rank[xroot] += 1

	def spanningTree(self, V, adj):
		edges = []
		for u in range(V):
			for (v, wt) in adj[u]:
				edges.append((u, v, wt))
		edges.sort(key=lambda x: x[2])
		parent = [i for i in range(V)]
		rank = [0] * V
		mst_weight = 0
		for (u, v, wt) in edges:
			uroot = Solution.find(parent, u)
			vroot = Solution.find(parent, v)
			if uroot != vroot:
				mst_weight += wt
				Solution.union(parent, rank, uroot, vroot)
		return mst_weight


from queue import PriorityQueue

class Solution:

	def spanningTree(self, V, adj):
		visited = set()
		pqueue = PriorityQueue()
		pqueue.put((0, 0, -1))
		mst_weight = 0
		while not pqueue.empty():
			(weight, u, v) = pqueue.get()
			if u in visited:
				continue
			visited.add(u)
			mst_weight += weight
			for (v, wt) in adj[u]:
				if v not in visited:
					pqueue.put((wt, v, u))
		return mst_weight


class Solution:

	def spanningTree(self, V, adj):
		parent = [-1 for hm in range(V)]

		def find(hm):
			while parent[hm] != -1:
				hm = parent[hm]
			return hm
		rank = [0 for hm in range(V)]
		memory = []
		cost = 0
		t = 0
		for hm in range(len(adj)):
			for gm in adj[hm]:
				memory.append([hm, gm[0], gm[1]])
		memory.sort(key=lambda x: x[2])
		for hm in memory:
			if t == V - 1:
				return cost
			if parent[hm[0]] != -1:
				parent[hm[0]] = find(hm[0])
			if parent[hm[1]] != -1:
				parent[hm[1]] = find(hm[1])
			x = find(hm[0])
			y = find(hm[1])
			if x == y:
				continue
			t += 1
			cost += hm[2]
			if rank[x] > rank[y]:
				parent[y] = x
				rank[x] += 1
			else:
				parent[x] = y
				rank[y] += 1
		return cost
		return cost


from heapq import heappop, heappush

class Solution:

	def spanningTree(self, V, adjList):
		heap = [(0, 0)]
		vis = [0 for _ in range(V)]
		minSum = 0
		while heap:
			(wt, node) = heappop(heap)
			if vis[node] == 1:
				continue
			vis[node] = 1
			minSum += wt
			for nei in adjList[node]:
				(currNode, currWt) = (nei[0], nei[1])
				if vis[currNode] != 1:
					heappush(heap, (currWt, currNode))
		return minSum


import heapq

class Solution:

	def spanningTree(self, V, adj):
		graph = {i: [] for i in range(V)}
		for i in range(V):
			graph[i].extend(adj[i])
		visited = set()
		pq = [[0, 0]]
		res = 0
		while pq:
			(cost, node) = heapq.heappop(pq)
			if node not in visited:
				visited.add(node)
				res += cost
				for (nei, neicost) in graph[node]:
					if nei not in visited:
						visited.add(node)
						heapq.heappush(pq, [neicost, nei])
		return res


import heapq

class Solution:

	def spanningTree(self, V, adj):
		pq = []
		heapq.heapify(pq)
		heapq.heappush(pq, [0, 0])
		s = 0
		vis = [0] * V
		while pq:
			(dis, node) = heapq.heappop(pq)
			if vis[node] == 1:
				continue
			vis[node] = 1
			s += dis
			for i in adj[node]:
				adjNode = i[0]
				edW = i[1]
				if vis[adjNode] == 0:
					heapq.heappush(pq, [edW, adjNode])
		return s


class Solution:

	def findParent(self, parent, node):
		if parent[node] == node:
			return node
		parent[node] = self.findParent(parent, parent[node])
		return parent[node]

	def unionSet(self, u, v, parent, rank):
		u = self.findParent(parent, u)
		v = self.findParent(parent, v)
		if rank[u] < rank[v]:
			parent[u] = v
		elif rank[v] < rank[u]:
			parent[v] = u
		else:
			parent[v] = u
			rank[u] += 1

	def spanningTree(self, V, adj):
		adjList = []
		for i in range(len(adj)):
			for j in range(len(adj[i])):
				adj[i][j].insert(0, i)
				adjList.append(adj[i][j])
		adjList.sort(key=lambda x: x[2])
		parent = [i for i in range(V)]
		rank = [0] * V
		minCost = 0
		for i in range(len(adjList)):
			u = self.findParent(parent, adjList[i][0])
			v = self.findParent(parent, adjList[i][1])
			wt = adjList[i][2]
			if u != v:
				minCost += wt
				self.unionSet(u, v, parent, rank)
		return minCost


from heapq import heappush, heappop

class Solution:

	def spanningTree(self, V, adj):
		summ = 0
		hp = []
		heappush(hp, (0, 0, -1))
		visited = [0] * V
		while hp:
			(cost, node, par) = heappop(hp)
			if visited[node]:
				continue
			visited[node] = 1
			summ += cost
			for (nghbr, wt) in adj[node]:
				if not visited[nghbr]:
					heappush(hp, (wt, nghbr, node))
		return summ


from collections import defaultdict

class Solution:

	def spanningTree(self, V, adj):
		cost = [10000000000.0] * V
		mst = [False] * V
		parent = [-1] * V
		cost[0] = 0
		mst[0] = True
		for i in range(V - 1):
			mini = 10000000000.0
			u = 0
			for j in range(V):
				if mst[j] == False and cost[j] < mini:
					u = j
					mini = cost[j]
			mst[u] = True
			for neighbor in adj[u]:
				child = neighbor[0]
				childCost = neighbor[1]
				if mst[child] == False and childCost < cost[child]:
					cost[child] = childCost
					parent[child] = u
		res = []
		ans = 0
		for i in range(1, V):
			res.append((parent[i], i, cost[i]))
			ans += cost[i]
		return ans


import heapq

class Solution:

	def spanningTree(self, V, adj):
		self.count = -1
		total_min_weight = 0
		min_spanning_tree = [False] * V
		min_weights = []
		weight_props = {}
		for i in range(V):
			self.count += 1
			vertex_props = [float('inf'), self.count, i]
			min_weights.append(vertex_props)
			weight_props[i] = vertex_props
		min_weights[0][0] = 0
		heapq.heapify(min_weights)
		for _ in range(V):
			(weight, _, vertex) = self.get_min_vertex(min_weights, weight_props)
			min_spanning_tree[vertex] = True
			total_min_weight += weight
			for (adjacent, wt) in adj[vertex]:
				if not min_spanning_tree[adjacent] and wt < weight_props[adjacent][0]:
					adj_vertex = weight_props.pop(adjacent)
					adj_vertex[-1] = None
					self.count += 1
					new_vertex = [wt, self.count, adjacent]
					weight_props[adjacent] = new_vertex
					heapq.heappush(min_weights, new_vertex)
		return total_min_weight

	def get_min_vertex(self, priority_queue, indexes):
		min_vertex = None
		while priority_queue:
			vertex_props = heapq.heappop(priority_queue)
			(_, __, vertex) = vertex_props
			if vertex is not None:
				del indexes[vertex]
				min_vertex = vertex_props
				break
		return min_vertex


class Disjoint:

	def __init__(self, v):
		self.rank = [0] * v
		self.parent = []
		for i in range(v):
			self.parent.append(i)

	def findPar(self, node):
		if node == self.parent[node]:
			return node
		else:
			self.parent[node] = self.findPar(self.parent[node])
			return self.parent[node]

	def union(self, u, v):
		paru = self.findPar(u)
		parv = self.findPar(v)
		if parv == paru:
			return
		elif self.rank[paru] < self.rank[parv]:
			self.parent[paru] = parv
		elif self.rank[parv] < self.rank[paru]:
			self.parent[parv] = paru
		else:
			self.parent[paru] = parv
			self.rank[parv] += 1

class Solution:

	def spanningTree(self, V, adj):
		edges = []
		res = 0
		for i in range(V):
			for (j, k) in adj[i]:
				edges.append((k, i, j))
		edges.sort()
		u = Disjoint(V)
		for (cost, i, j) in edges:
			if u.findPar(i) != u.findPar(j):
				res += cost
				u.union(i, j)
		return res


import heapq

class Solution:

	def spanningTree(self, V, adj):
		q = [(0, 0)]
		res = 0
		vis = set()
		while q:
			(cost, node) = heapq.heappop(q)
			if node in vis:
				continue
			vis.add(node)
			res += cost
			for (nei, c) in adj[node]:
				if nei not in vis:
					heapq.heappush(q, (c, nei))
		return res


import heapq

class Solution:

	def spanningTree(self, V, adj):
		q = [(0, 0, -1)]
		res = 0
		vis = [False] * V
		while q:
			(cost, node, parent) = heapq.heappop(q)
			if vis[node]:
				continue
			vis[node] = True
			res += cost
			for (nei, val) in adj[node]:
				if vis[nei] == False:
					heapq.heappush(q, (val, nei, node))
		return res


class Solution:

	def spanningTree(self, V, adj):
		edges = []
		for i in range(V):
			for it in adj[i]:
				adjnode = it[0]
				wt = it[1]
				node = i
				edges.append((wt, node, adjnode))
		edges.sort()
		ds = disjoint(V)
		mwt = 0
		for it in edges:
			wt = it[0]
			node = it[1]
			adjnode = it[2]
			if ds.findUPar(node) != ds.findUPar(adjnode):
				mwt += wt
				ds.unionrank(node, adjnode)
		return mwt

class disjoint:

	def __init__(self, n):
		self.rank = [0] * (n + 1)
		self.parent = [0] * (n + 1)
		for i in range(n):
			self.parent[i] = i

	def findUPar(self, node):
		if node == self.parent[node]:
			return node
		return self.findUPar(self.parent[node])

	def unionrank(self, u, v):
		Up_u = self.findUPar(u)
		Up_v = self.findUPar(v)
		if Up_u == Up_v:
			return
		if self.rank[Up_u] < self.rank[Up_v]:
			self.parent[Up_u] = Up_v
		elif self.rank[Up_v] < self.rank[Up_u]:
			self.parent[Up_v] = Up_u
		else:
			self.parent[Up_v] = Up_u
			self.rank[Up_u] += 1


import math
from typing import List, Optional, Tuple, Union
import sys

class Solution:

	def _transform(V, adj):
		adj_m = [[math.inf] * V for _ in range(V)]
		for i in range(len(adj)):
			for (j, c) in adj[i]:
				adj_m[i][j] = c
		return adj_m

	def _get_edge_list(graph: List[List[Union[int, float]]]) -> List[Tuple[int, int, Union[int, float]]]:
		edge_list = []
		V = len(graph)
		for u in range(1, V):
			for v in range(u):
				if not math.isinf(graph[u][v]):
					edge_list.append((u, v, graph[u][v]))
		return edge_list

	def collapsing_find(u: int, parent: List[int]) -> int:
		i = u
		while parent[i] >= 0:
			i = parent[i]
		initial_u_p = parent[u]
		while initial_u_p >= 0:
			parent[u] = i
			u = initial_u_p
			initial_u_p = parent[u]
		return i

	def union(u: int, v: int, parent: List[int]) -> None:
		u_p = Solution.collapsing_find(u, parent)
		v_p = Solution.collapsing_find(v, parent)
		if u_p == v_p:
			return
		if parent[u_p] < parent[v_p]:
			parent[u_p] += parent[v_p]
			parent[v_p] = u_p
		else:
			parent[v_p] += parent[u_p]
			parent[u_p] = v_p

	def spanningTree(self, V, adj):
		adj = Solution._transform(V, adj)
		V = len(adj)
		edge_list = Solution._get_edge_list(adj)
		edge_list_s = sorted(edge_list, key=lambda e: e[2])
		mst_edges = [None] * (V - 1)
		vertex_set = [-1] * V
		mst_edge_i = 0
		for (edge_i, edge) in enumerate(edge_list_s):
			a = Solution.collapsing_find(edge[0], vertex_set)
			b = Solution.collapsing_find(edge[1], vertex_set)
			if a != b:
				mst_edges[mst_edge_i] = edge
				Solution.union(edge[0], edge[1], vertex_set)
				mst_edge_i += 1
			if mst_edge_i == V - 1:
				break
		return sum((edge[2] for edge in mst_edges))


class Solution:

	def spanningTree(self, V, adj):
		import heapq
		vis = [0] * V
		min_heap = []
		min_heap.append((0, 0, -1))
		ans = 0
		while min_heap:
			(wei, node, parent) = heapq.heappop(min_heap)
			if vis[node]:
				continue
			ans += wei
			vis[node] = 1
			for (n, w) in adj[node]:
				if not vis[n]:
					heapq.heappush(min_heap, (w, n, node))
		return ans


import math
from typing import List, Optional, Union
import sys

class Solution:

	def _transform(V, adj):
		adj_m = [[math.inf] * V for _ in range(V)]
		for i in range(len(adj)):
			for (j, c) in adj[i]:
				adj_m[i][j] = c
		return adj_m

	def _get_min_edge(adj: List[List[Union[int, float]]]):
		min_dist = math.inf
		min_edge = None
		V = len(adj)
		for u in range(1, V):
			for v in range(u):
				if adj[u][v] < min_dist:
					min_dist = adj[u][v]
					min_edge = (u, v)
		return min_edge

	def spanningTree(self, V, adj):
		adj = Solution._transform(V, adj)
		V = len(adj)
		mst_vertices = [False] * V
		near_to = [None] * V
		mst_edges = [None] * (V - 1)
		(u, v) = Solution._get_min_edge(adj)
		(mst_vertices[u], mst_vertices[v]) = (True, True)
		mst_edges[0] = (u, v)
		for vertex in range(V):
			if vertex != u and vertex != v:
				if adj[u][vertex] is not None and adj[v][vertex] is not None:
					near_to[vertex] = u if adj[u][vertex] < adj[v][vertex] else v
				elif adj[u][vertex] is not None:
					near_to[vertex] = u
				else:
					near_to[vertex] = v
		for edge_no in range(1, V - 1):
			min_dist = math.inf
			min_vertex = None
			for v in range(V):
				if not mst_vertices[v] and adj[v][near_to[v]] < min_dist:
					min_dist = adj[v][near_to[v]]
					min_vertex = v
			mst_vertices[min_vertex] = True
			mst_edges[edge_no] = (near_to[min_vertex], min_vertex)
			for v in range(V):
				if not mst_vertices[v] and adj[v][min_vertex] < adj[v][near_to[v]]:
					near_to[v] = min_vertex
		total = 0
		for (u, v) in mst_edges:
			total += adj[u][v]
		return total


from queue import PriorityQueue
import heapq as heap

class Solution:

	def spanningTree(self, V, adj):
		vis = [0] * V
		q = []
		heap.heappush(q, (0, 0))
		s = 0
		while q:
			(wt, node) = heap.heappop(q)
			if vis[node] == 1:
				continue
			vis[node] = 1
			s += wt
			for it in adj[node]:
				adjnode = it[0]
				weight = it[1]
				if vis[adjnode] == 0:
					heap.heappush(q, (weight, adjnode))
		return s


import heapq

class Solution:

	def spanningTree(self, V, adj):
		MST = []
		MSTs = 0
		visited = [False for _ in range(V)]
		pq = [(0, 0, -1)]
		while pq:
			(w, v, u) = heapq.heappop(pq)
			if visited[v]:
				continue
			visited[v] = True
			if not u == -1:
				MST.append((u, v))
				MSTs += w
			for (v1, w1) in adj[v]:
				heapq.heappush(pq, (w1, v1, v))
		return MSTs


from queue import PriorityQueue

class Solution:

	def spanningTree(self, V, adj):
		vis = [0] * V
		q = PriorityQueue()
		q.put((0, 0))
		s = 0
		while not q.empty():
			(wt, node) = q.get()
			if vis[node] == 1:
				continue
			vis[node] = 1
			s += wt
			for it in adj[node]:
				adjnode = it[0]
				weight = it[1]
				if vis[adjnode] == 0:
					q.put((weight, adjnode))
		return s


class Solution:

	def spanningTree(self, V, adj):
		total_min_weight = 0
		min_spanning_tree = [False] * V
		min_weights = [float('inf')] * V
		min_weights[0] = 0
		for _ in range(V):
			vertex = self.get_min_vertex(min_spanning_tree, min_weights)
			min_spanning_tree[vertex] = True
			total_min_weight += min_weights[vertex]
			for (adjacent, weight) in adj[vertex]:
				if not min_spanning_tree[adjacent] and weight < min_weights[adjacent]:
					min_weights[adjacent] = weight
		return total_min_weight

	def get_min_vertex(self, mst, weights):
		min_index = None
		_min = float('inf')
		for i in range(len(mst)):
			if not mst[i] and (min_index is None or weights[i] < _min):
				min_index = i
				_min = weights[i]
		return min_index


from queue import PriorityQueue

def spanning_tree(v, adj: [[[]]]):
	data_queue = PriorityQueue()
	visited = [False] * v
	data_queue.put((0, 0))
	answer = 0
	while len(data_queue.queue) > 0:
		vertex_weight_data = data_queue.get()
		vertex = vertex_weight_data[1]
		if visited[vertex]:
			continue
		visited[vertex] = True
		weight = vertex_weight_data[0]
		answer = answer + weight
		neighbours_weight_list = adj[vertex]
		for neighbour_weight in neighbours_weight_list:
			neighbour = neighbour_weight[0]
			weight = neighbour_weight[1]
			data_queue.put((weight, neighbour))
	return answer

class Solution:

	def spanningTree(self, V, adj):
		return spanning_tree(V + 1, adj)


class DisjointSet:

	def __init__(self, n):
		self.rank = [0] * (n + 1)
		self.parent = [i for i in range(n + 1)]

	def find(self, node):
		if node == self.parent[node]:
			return node
		self.parent[node] = self.find(self.parent[node])
		return self.parent[node]

	def union(self, u, v):
		pu = self.find(u)
		pv = self.find(v)
		if pu == pv:
			return
		if self.rank[pu] > self.rank[pv]:
			self.parent[pu] = pv
		elif self.rank[pv] > self.rank[pu]:
			self.parent[pv] = pu
		else:
			self.parent[pv] = pu
			self.rank[pu] += 1

class Solution:

	def spanningTree(self, V, adj):
		edges = []
		djs = DisjointSet(V)
		mst = 0
		for u in range(V):
			for (v, w) in adj[u]:
				edges.append((w, u, v))
		edges.sort(key=lambda x: x[0])
		for (w, u, v) in edges:
			if djs.find(u) != djs.find(v):
				mst += w
				djs.union(u, v)
		return mst


class Solution:

	def spanningTree(self, V, adj):
		total_minimum_weight = 0
		minimum_spanning_tree = [False] * V
		minimum_weights = [float('inf')] * V
		minimum_weights[0] = 0
		for _ in range(V):
			minimum_vertex = self.get_minimum_vertex(minimum_spanning_tree, minimum_weights)
			minimum_spanning_tree[minimum_vertex] = True
			total_minimum_weight += minimum_weights[minimum_vertex]
			for (adjacent, weight) in adj[minimum_vertex]:
				if not minimum_spanning_tree[adjacent] and weight < minimum_weights[adjacent]:
					minimum_weights[adjacent] = weight
		return total_minimum_weight

	def get_minimum_vertex(self, minimum_spanning_tree, minimum_weights):
		index = None
		minimum = float('inf')
		for (i, weight) in enumerate(minimum_weights):
			if not minimum_spanning_tree[i] and (index is None or weight < minimum):
				index = i
				minimum = weight
		return index


class Solution:

	def spanningTree(self, V, adj):
		total_min_weight = 0
		mst_members = [False] * V
		min_weights = [float('inf')] * V
		min_weights[0] = 0
		for _ in range(V):
			min_vertex = self.get_min_vertex(mst_members, min_weights, V)
			mst_members[min_vertex] = True
			total_min_weight += min_weights[min_vertex]
			for (adjacent, weight) in adj[min_vertex]:
				if not mst_members[adjacent] and weight < min_weights[adjacent]:
					min_weights[adjacent] = weight
		return total_min_weight

	def get_min_vertex(self, mst, weights, V):
		index = None
		minimum = float('inf')
		for vertex in range(V):
			if not mst[vertex] and (index is None or weights[vertex] < minimum):
				index = vertex
				minimum = weights[vertex]
		return index


class Solution:

	def spanningTree(self, V, adj):
		minimum_weights = [float('inf')] * V
		minimum_weights[0] = 0
		minimum_spanning_tree = [False] * V
		sum_of_weights = 0
		for _ in range(V):
			vertex = self.get_minimum_vertex(minimum_weights, minimum_spanning_tree, V)
			minimum_spanning_tree[vertex] = True
			sum_of_weights += minimum_weights[vertex]
			for (adjacent, weight) in adj[vertex]:
				if not minimum_spanning_tree[adjacent] and weight < minimum_weights[adjacent]:
					minimum_weights[adjacent] = weight
		return sum_of_weights

	def get_minimum_vertex(self, minimum_weights, minimum_spanning_tree, V):
		min_index = None
		_min = float('inf')
		for v in range(V):
			if not minimum_spanning_tree[v] and (min_index is None or minimum_weights[v] < _min):
				min_index = v
				_min = minimum_weights[v]
		return min_index


import heapq

class Solution:

	def spanningTree(self, V, adj):
		vis = set()
		wt = 0
		queue = [(0, 0)]
		while queue:
			(w, node) = heapq.heappop(queue)
			if node not in vis:
				wt += w
				vis.add(node)
				for (nei, wei) in adj[node]:
					if nei not in vis:
						heapq.heappush(queue, (wei, nei))
		return wt


import heapq

class Solution:

	def spanningTree(self, V, adj):
		vis = [0] * V
		pq = []
		sum = 0
		heapq.heappush(pq, [0, 0])
		while pq:
			s = heapq.heappop(pq)
			u = s[1]
			w = s[0]
			if vis[u] == 1:
				continue
			vis[u] = 1
			sum += w
			for i in adj[u]:
				v = i[0]
				wt = i[1]
				if vis[v] == 0:
					heapq.heappush(pq, [wt, v])
		return sum


import heapq

class Solution:

	def spanningTree(self, V, adj):
		vis = [0] * V
		dist = [float('inf')] * V
		pq = []
		pq.append((0, 0))
		dist[0] = 0
		mst = 0
		while pq:
			(w1, u) = heapq.heappop(pq)
			if vis[u] == 1:
				continue
			mst += w1
			vis[u] = 1
			for (v, w2) in adj[u]:
				heapq.heappush(pq, (w2, v))
		return mst


from collections import defaultdict
import heapq

class Solution:

	def spanningTree(self, V, adj):
		visit = set()
		pq = [[0, 0]]
		res = 0
		while pq:
			(cost, node) = heapq.heappop(pq)
			if node not in visit:
				visit.add(node)
				res += cost
				for (nei, neicost) in adj[node]:
					if nei not in visit:
						heapq.heappush(pq, [neicost, nei])
		return res


class DSU:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.rank = [0] * n

	def find(self, x):
		if self.parent[x] == x:
			return x
		self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, src, dest):
		(x_parent, y_parent) = (self.find(src), self.find(dest))
		if x_parent != y_parent:
			if self.rank[x_parent] < self.rank[y_parent]:
				self.parent[x_parent] = y_parent
			elif self.rank[x_parent] > self.rank[y_parent]:
				self.parent[y_parent] = x_parent
			else:
				self.parent[x_parent] = y_parent
				self.rank[y_parent] += 1
			return True
		return False

class Solution:

	def spanningTree(self, n, edges):
		graph = []
		for i in range(n):
			for j in adj[i]:
				dest = j[0]
				cost = j[1]
				graph.append([cost, i, dest])
		graph.sort()
		ans = 0
		build_graph = DSU(n)
		for (cost, src, dest) in graph:
			if build_graph.union(src, dest):
				ans += cost
		return ans


from collections import defaultdict
from heapq import heapify, heappush, heappop

class Solution:

	def spanningTree(self, n, adj):
		edges = {}
		for i in range(0, len(adj)):
			for j in adj[i]:
				edges[i, j[0]] = j[1]
				edges[j[0], i] = j[1]
		dis = [float('inf') for i in range(0, n)]
		inMST = [False for i in range(0, n)]
		parent = [-1 for i in range(0, n)]
		pq = []
		heapify(pq)
		heappush(pq, (0, 0))
		dis[0] = 0
		visited = 0
		total = 0
		while pq:
			(cost, u) = heappop(pq)
			inMST[u] = True
			visited += 1
			for i in range(0, len(adj[u])):
				(v, new_cost) = (adj[u][i][0], adj[u][i][1])
				if dis[v] > new_cost and inMST[v] == False:
					dis[v] = new_cost
					parent[v] = u
					heappush(pq, (dis[v], v))
		for i in range(0, n):
			if i != 0:
				p = parent[i]
				total += edges[i, p]
		return total


import heapq

class Solution:

	def spanningTree(self, V, adj):
		dist = []
		n = len(adj)
		for i in range(n):
			for j in adj[i]:
				dist.append((j[1], i, j[0]))
		heapq.heapify(dist)
		par = [i for i in range(V)]
		mstsum = 0
		while n > 1:
			(d, i, j) = heapq.heappop(dist)
			(pari, parj) = (i, j)
			while par[pari] != pari:
				pari = par[pari]
			while par[parj] != parj:
				parj = par[parj]
			if pari != parj:
				n = n - 1
				par[pari] = parj
				mstsum = mstsum + d
		return mstsum


def find_parent(u, parent):
	if parent[u] != u:
		parent[u] = find_parent(parent[u], parent)
	return parent[u]

def find_union(dis, u, v, parent, rank):
	parent_u = find_parent(u, parent)
	parent_v = find_parent(v, parent)
	if parent_u == parent_v:
		return 0
		pass
	else:
		if rank[parent_u] > rank[parent_v]:
			rank[parent_u] += rank[parent_v]
			parent[parent_v] = parent_u
		if rank[parent_v] > rank[parent_u]:
			rank[parent_v] += rank[parent_u]
			parent[parent_u] = parent_v
		else:
			rank[parent_u] += rank[parent_v]
			parent[parent_v] = parent_u
		return dis

class Solution:

	def spanningTree(self, V, adj):
		parent = {}
		rank = {}
		new_adj = []
		d = {}
		for i in range(V):
			d[i] = []
			parent[i] = i
			rank[i] = 1
		for i in range(len(adj)):
			for j in range(len(adj[i])):
				if adj[i][j][0] not in d[i]:
					d[i].append(adj[i][j][0])
					d[adj[i][j][0]].append(i)
					new_adj.append([adj[i][j][1], i, adj[i][j][0]])
		new_adj.sort()
		total = 0
		store = []
		for (dis, u, v) in new_adj:
			store.append(find_union(dis, u, v, parent, rank))
			total += store[-1]
		return total


from heapq import *

class Solution:

	def spanningTree(self, n, edges):
		visited = [False] * n
		graph = [[-1 for j in range(n)] for i in range(n)]
		for i in range(n):
			for j in adj[i]:
				dest = j[0]
				cost = j[1]
				graph[i][dest] = cost
		min_heap = []
		heappush(min_heap, (0, 0))
		sum1 = 0
		while min_heap:
			(dist, node) = heappop(min_heap)
			if visited[node] == False:
				visited[node] = True
				sum1 += dist
				for nbr in range(n):
					if graph[node][nbr] != -1:
						heappush(min_heap, (graph[node][nbr], nbr))
		return sum1