The kingdom of Zion has cities connected by bidirectional roads.  There is a unique path between any pair of cities. Morpheus has found out that the machines are planning to destroy the whole kingdom.  If two machines can join forces, they will attack.  Neo has to destroy roads connecting cities with machines in order to stop them from joining forces.  There must not be any path connecting two machines.

Each of the roads takes an amount of time to destroy, and only one can be worked on at a time.  Given a list of edges and times, determine the minimum time to stop the attack.

For example, there are $n=5$ cities called $\mathbf{0}-4$.  Three of them have machines and are colored red.  The time to destroy is shown next to each road.  If we cut the two green roads, there are no paths between any two machines.  The time required is $3+2=5$.  

Function Description

Complete the function minTime in the editor below.  It must return an integer representing the minimum time to cut off access between the machines.

minTime has the following parameter(s):

roads: a two-dimensional array of integers, each $roads[i]=[city1,city2,time]$ where cities are connected by a road that takes $\textbf{time}$ to destroy  
machines: an array of integers representing cities with machines  

Input Format

The first line of the input contains two space-separated integers, $n$ and $\boldsymbol{\mbox{k}}$, the number of cities and the number of machines.  

Each of the following $n-1$ lines contains three space-separated integers, $\textit{city1},\textit{city2}$, and $\textbf{time}$.  There is a bidirectional road connecting $\text{city1}$ and $\text{city2}$, and to destroy this road it takes $\textbf{time}$ units.

Each of the last $\boldsymbol{\mbox{k}}$ lines contains an integer, $\textit{machine}[i]$, the label of a city with a machine.   

Constraints

$2\leq n\leq10^5$  
$2\leq k\leq n$  
$1\leq time[i]\leq10^6$  

Output Format

Return an integer representing the minimum time required to disrupt the connections among all machines.

Sample Input
5 3
2 1 8
1 0 5
2 4 5
1 3 4
2
4
0

Sample Output
10

Explanation

The machines are located at the cities $0$, $2$ and $4$. Neo can destroy the green roads resulting in a time of $5+5=10$.  Destroying the road between cities $2$ and $1$ instead of between $1$ and $0$ would work, but it's not minimal.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Graph algorithms


Solutions:
def leader(x):
	if P[x] == x:
		return P[x]
	if P[x] == x + 10 ** 5:
		return P[x]
	P[x] = leader(P[x])
	return P[x]

def same(x, y):
	return leader(x) == leader(y)

def canJoin(x, y):
	return not (leader(x) >= 10 ** 5 and leader(y) >= 10 ** 5)

def union(x, y):
	a = leader(x)
	b = leader(y)
	if a > b:
		(a, b) = (b, a)
	S[b] += S[a]
	P[a] = b
(n, k) = list(map(int, input().split()))
lis = []
for _ in range(n - 1):
	(x, y, z) = list(map(int, input().split()))
	lis.append((x, y, z))
lis.sort(key=lambda x: -x[2])
P = {x: x for x in range(n)}
S = {x: 1 for x in range(n)}
for _ in range(k):
	r = int(input())
	P[r + 10 ** 5] = r + 10 ** 5
	P[r] = r + 10 ** 5
	S[r + 10 ** 5] = 1
res = 0
for (x, y, z) in lis:
	if canJoin(x, y):
		union(x, y)
	else:
		res += z
print(res)


class vertex:

	def __init__(self):
		self.adj = []
		self.is_k = False

def find_smallest_edge_and_delete(arr, edg_lst):
	if len(edg_lst) == 0:
		return 0
	smallest = edg_lst[0]
	for edge in edg_lst:
		if smallest[2] > edge[2]:
			smallest = edge
	arr[smallest[0]].adj.remove([smallest[1], smallest[2]])
	arr[smallest[1]].adj.remove([smallest[0], smallest[2]])
	return smallest[2]

def BFS_and_del(arr, x, edg_lst, visited):
	visited[x] = True
	val = 0
	for edge in arr[x].adj:
		if edge[0] in visited:
			continue
		edg_lst.append([x, edge[0], edge[1]])
		if arr[edge[0]].is_k == True:
			val = find_smallest_edge_and_delete(arr, edg_lst)
		else:
			val = BFS_and_del(arr, edge[0], edg_lst, visited)
		edg_lst.remove([x, edge[0], edge[1]])
		if val != 0:
			break
	del visited[x]
	return val
var = input().split()
(N, K) = (int(var[0]), int(var[1]))
V = []
arrK = []
for i in range(0, N):
	V.append(vertex())
for i in range(0, N - 1):
	var = input().split()
	(x, y, w) = (int(var[0]), int(var[1]), int(var[2]))
	V[x].adj.append([y, w])
	V[y].adj.append([x, w])
for i in range(0, K):
	val = int(input())
	V[val].is_k = True
	arrK.append(val)
ans = 0
del_count = 0
while del_count < K - 1:
	for k in arrK:
		val = BFS_and_del(V, k, [], {})
		if val > 0:
			del_count += 1
			ans = ans + val
print(ans)


def root(v):
	if par[v] == v:
		return v
	par[v] = root(par[v])
	return par[v]

def merge(x, y):
	if root(x) in c:
		par[y] = root(x)
	else:
		par[x] = root(y)
(n, k) = map(int, input().split())
g = [list(map(int, input().split())) for _ in range(n - 1)]
c = {int(input()) for _ in range(k)}
r = 0
par = [u for u in range(n)]
for (u, v, w) in sorted(g, key=lambda x: -x[2]):
	if root(u) in c and root(v) in c:
		r += w
		continue
	merge(root(u), root(v))
print(r)


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

def merge(x, y):
	x = find(x)
	y = find(y)
	if x != y:
		if s[x] > s[y]:
			p[y] = x
			s[x] += s[y]
		else:
			p[x] = y
			s[y] += s[x]
(n, k) = map(int, input().split())
p = list(range(n))
s = [1] * n
m = [False] * n
e = []
for _ in range(n - 1):
	(x, y, r) = map(int, input().split())
	e.append((r, x, y))
for _ in range(k):
	i = int(input())
	m[i] = True
e = sorted(e, reverse=True)
c = 0
for (r, x, y) in e:
	x = find(x)
	y = find(y)
	if not (m[x] and m[y]):
		merge(x, y)
		m[x] = m[x] or m[y]
		m[y] = m[x]
	else:
		c += r
print(c)


import random

def Find(uf, u):
	if uf[u] != u:
		uf[u] = Find(uf, uf[u])
	return uf[u]

def Sol(E, mlocs, N):
	uf = list(range(N))
	E = sorted(E)
	res = 0
	while E:
		(w, u, v) = E.pop()
		if Find(uf, u) in mlocs and Find(uf, v) in mlocs:
			res += w
			continue
		if random.randint(0, 1):
			if Find(uf, u) in mlocs:
				mlocs.add(Find(uf, v))
			uf[Find(uf, u)] = Find(uf, v)
		else:
			if Find(uf, v) in mlocs:
				mlocs.add(Find(uf, u))
			uf[Find(uf, v)] = Find(uf, u)
	return res
(N, K) = map(int, input().split())
E = set()
mlocs = set()
for _ in range(N - 1):
	(u, v, w) = map(int, input().split())
	E.add((w, u, v))
for _ in range(K):
	u = int(input())
	mlocs.add(u)
print(Sol(E, mlocs, N))


(N, K) = map(int, input().split())
G = [[] for i in range(N)]
for i in range(N - 1):
	(x, y, z) = map(int, input().split())
	G[x].append((y, z))
	G[y].append((x, z))
machine = [False] * N
for i in range(K):
	x = int(input())
	machine[x] = True

def cost(i, p):
	tot = 0
	save = 0
	for (j, c) in G[i]:
		if j != p:
			(c0, c1) = cost(j, i)
			m = min(c0, c1 + c)
			tot += m
			s = m - c1
			if s > save:
				save = s
	if machine[i]:
		return (10 ** 11, tot)
	return (tot, tot - save)
print(min(cost(0, 0)))


class DisjointSets(object):

	def __init__(self):
		self.disjoints = {}
		self.root_to_machines = {}

	def add_root(self, elem, is_machine):
		self.disjoints[elem] = elem
		if is_machine:
			self.root_to_machines[elem] = set([elem])
		else:
			self.root_to_machines[elem] = set()

	def find_root(self, elem):
		curr = self.disjoints[elem]
		path_comp = []
		while curr != self.disjoints[curr]:
			curr = self.disjoints[curr]
			path_comp.append(curr)
		for el in path_comp:
			self.disjoints[el] = curr
		return curr

	def union(self, e1, e2):
		root1 = self.find_root(e1)
		root2 = self.find_root(e2)
		self.disjoints[root1] = root2
		self.root_to_machines[root2] = self.root_to_machines[root1].union(self.root_to_machines[root2])

	def test_roots(self, e1, e2, machine_locs):
		root1 = self.find_root(e1)
		root2 = self.find_root(e2)
		if root1 == root2:
			return False
		machines1 = self.root_to_machines[root1]
		machines2 = self.root_to_machines[root2]
		return len(machines1) == 0 or len(machines2) == 0

def remove_roads(graph, edge_dists, machines):
	sorted_edges = sorted(edge_dists, key=lambda x: -x[2])
	disj_set = DisjointSets()
	for node in range(len(graph)):
		disj_set.add_root(node, node in machines)
	del_edges = []
	del_sum = 0
	for (x, y, r) in sorted_edges:
		if not disj_set.test_roots(x, y, machines):
			del_edges.append((x, y))
			del_sum += r
		else:
			disj_set.union(x, y)
	return del_sum
(n, k) = tuple([int(i) for i in input().strip().split()])
machines = set()
graph = [{} for _ in range(n)]
edge_dists = []
for a0 in range(n - 1):
	(x, y, r) = tuple((int(i) for i in input().strip().split(' ')))
	graph[x] = y
	edge_dists.append((x, y, r))
for a1 in range(k):
	machines.add(int(input().strip()))
print(remove_roads(graph, edge_dists, machines))


class Edge(object):

	def __init__(self, city1: int, city2: int, weight: int):
		self.cities = [city1, city2]
		self.weight = weight
[N, K] = [int(i) for i in input().split(' ')]
edges = list()
for i in range(N - 1):
	line = input()
	[city1, city2, weight] = [int(j) for j in line.split(' ')]
	edges.append(Edge(city1, city2, weight))
edges.sort(key=lambda x: x.weight, reverse=True)
cityToGroup = dict()
machineCities = dict()
for i in range(K):
	mc = int(input())
	machineCities[mc] = True
	cityToGroup[mc] = mc
result = 0
groups = dict()
for i in range(N):
	groups[i] = [i]
	cityToGroup[i] = i
for e in edges:
	city1 = e.cities[0]
	city2 = e.cities[1]
	g1 = cityToGroup[city1]
	g2 = cityToGroup[city2]
	if g1 == g2:
		continue
	if machineCities.get(g1, None) is not None:
		if machineCities.get(g2, None) is not None:
			result += e.weight
		else:
			for c in groups[g2]:
				cityToGroup[c] = g1
				groups[g1].append(c)
			del groups[g2]
	else:
		for c in groups[g1]:
			groups[g2].append(c)
			cityToGroup[c] = g2
		del groups[g1]
print(result)


class Graph:

	def __init__(self, N):
		self.nodes_ = [[] for n in range(N)]

	def add_edge(self, a, b, cost):
		neighbors = self.nodes_[a]
		for (i, (n, z)) in enumerate(neighbors):
			if n == b:
				neighbors[i] = (n, z + cost)
				return
		neighbors.append((b, cost))

	def get_edges(self):
		return [(x, y, z) for (x, neighbors) in enumerate(self.nodes_) for (y, z) in neighbors]

class Cluster:

	def __init__(self, n=-1, is_machine=False):
		self.nodes = set()
		if n != -1:
			self.nodes.add(n)
		self.is_machine = is_machine

	@staticmethod
	def union(a, b):
		c = Cluster()
		c.is_machine = a.is_machine or b.is_machine
		c.nodes = a.nodes | b.nodes
		return c
(N, K) = map(int, input().split())
g = Graph(N)
for n in range(N - 1):
	(x, y, z) = map(int, input().split())
	g.add_edge(x, y, z)
clusters = [Cluster(n, False) for n in range(N)]
for k in range(K):
	n = int(input())
	clusters[n].is_machine = True
edges = g.get_edges()
edges.sort(key=lambda x_y_z: x_y_z[2], reverse=True)
destroy = 0
for (x, y, z) in edges:
	cx = clusters[x]
	cy = clusters[y]
	if cx.is_machine and cy.is_machine:
		destroy += z
		continue
	r = Cluster.union(cx, cy)
	for n in r.nodes:
		clusters[n] = r
print(destroy)


(n, k) = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(n - 1):
	(x, y, z) = map(int, input().split())
	adj[x].append((y, z))
	adj[y].append((x, z))
machine = [False] * n
for _ in range(k):
	machine[int(input())] = True
BIG = 10 ** 9
cost0 = [BIG] * n
cost1 = [BIG] * n

def dfs(p, v):
	for pair in adj[v]:
		if pair[0] == p:
			adj[v].remove(pair)
			break
	for (u, z) in adj[v]:
		dfs(v, u)
	costs = {u: min(cost0[u] + z, cost1[u]) for (u, z) in adj[v]}
	sumcosts = sum(costs.values())
	if machine[v]:
		cost1[v] = BIG
		cost0[v] = sumcosts
	else:
		cost1[v] = sumcosts
		diffs = [cost0[u] - costs[u] for (u, z) in adj[v] if cost0[u] < BIG]
		if len(diffs) == 0:
			cost0[v] = BIG
		else:
			cost0[v] = min(diffs) + sumcosts
dfs(0, 0)
print(min(cost0[0], cost1[0]))


class City:

	def __init__(self, id):
		self.id = id
		self.has_machine = id in machine_ids
		self.friends = set()
		self.machines = set()

	def add_neighbor(self, neighbor):
		if neighbor.has_machine:
			self.machines.add(neighbor)
		else:
			self.friends.add(neighbor)

	def del_neighbor(self, neighbor):
		if neighbor.has_machine:
			self.machines.remove(neighbor)
		else:
			self.friends.remove(neighbor)

def pop_road(city1, city2):
	cities[city1.id].del_neighbor(city2)
	cities[city2.id].del_neighbor(city1)
	return road_weights.pop(frozenset({city1.id, city2.id}))
(N, K) = (int(x) for x in input().split())
road_weights = {}
for i in range(N - 1):
	(city_id1, city_id2, weight) = (int(x) for x in input().split())
	road_weights[frozenset({city_id1, city_id2})] = weight
machine_ids = set()
for i in range(K):
	machine_ids.add(int(input()))
cities = {}
for road in road_weights:
	for city_id in road:
		if city_id not in cities:
			cities[city_id] = City(city_id)
	(city_id1, city_id2) = road
	cities[city_id1].add_neighbor(cities[city_id2])
	cities[city_id2].add_neighbor(cities[city_id1])
time = 0
priorities = set(cities.values())
while len(road_weights) > 0:
	city = priorities.pop()
	if city.has_machine:
		if len(city.machines) > 0:
			for machine in city.machines.copy():
				time += pop_road(city, machine)
				priorities.add(machine)
	else:
		if len(city.machines) > 1:
			(max_machine, max_weight) = (0, 0)
			for machine in city.machines:
				weight = road_weights[frozenset({city.id, machine.id})]
				if weight > max_weight:
					(max_machine, max_weight) = (machine, weight)
			for machine in city.machines.copy():
				if machine != max_machine:
					time += pop_road(city, machine)
					priorities.add(machine)
		if len(city.friends) + len(city.machines) == 1:
			(neighbor,) = city.friends | city.machines
			pop_road(city, neighbor)
			priorities.add(neighbor)
		elif len(city.friends) + len(city.machines) == 2:
			(neighbor1, neighbor2) = city.friends | city.machines
			(road1, road2) = (frozenset({city.id, neighbor1.id}), frozenset({city.id, neighbor2.id}))
			road_weights[frozenset({neighbor1.id, neighbor2.id})] = min(road_weights[road1], road_weights[road2])
			neighbor1.add_neighbor(neighbor2)
			neighbor2.add_neighbor(neighbor1)
			pop_road(city, neighbor1)
			pop_road(city, neighbor2)
			priorities |= {neighbor1, neighbor2}
print(time)


class DisjointSet:

	class Node:

		def __init__(self, ID, rank=0):
			self.id = ID
			self.parent = self.id
			self.rank = rank
			self.has_robot = False

	def __init__(self, n, robot_nodes=[]):
		self.nodes = [DisjointSet.Node(x) for x in range(n)]
		for x in robot_nodes:
			self.nodes[x].has_robot = True

	def find(self, x):
		n = self.nodes[x]
		update_list = []
		while n.id != n.parent:
			update_list.append(n)
			n = self.nodes[n.parent]
		for x in update_list:
			x.parent = n.parent
		return n.parent

	def is_disjoint(self, x, y):
		return self.find(x) != self.find(y)

	def has_robot(self, x):
		return self.nodes[self.find(x)].has_robot

	def union(self, x, y):
		x_id = self.find(x)
		y_id = self.find(y)
		if x_id == y_id:
			return
		x_root = self.nodes[x_id]
		y_root = self.nodes[y_id]
		if x_root.rank < y_root.rank:
			x_root.parent = y_id
			y_root.has_robot = x_root.has_robot or y_root.has_robot
		elif x_root.rank > y_root.rank:
			y_root.parent = x_id
			x_root.has_robot = x_root.has_robot or y_root.has_robot
		else:
			x_root.parent = y_id
			y_root.rank += 1
			y_root.has_robot = x_root.has_robot or y_root.has_robot
(n, k) = [int(x) for x in input().split()]
E = [tuple((int(x) for x in input().split())) for _ in range(n - 1)]
robot_nodes = [int(input()) for _ in range(k)]
ds = DisjointSet(n, robot_nodes)
E.sort(key=lambda xyw: xyw[2], reverse=True)
res = 0
for (x, y, w) in E:
	if not ds.is_disjoint(x, y):
		continue
	if ds.has_robot(x) and ds.has_robot(y):
		res += w
		continue
	ds.union(x, y)
print(res)


from collections import defaultdict
from operator import itemgetter
import heapq
import sys

def find_city_to_disconnect(start_city, end_cities, citymap):
	paths = defaultdict(list)
	visited = set([start_city])
	queue = [(0, start_city)]
	heapq.heapify(queue)
	time = {start_city: 0}
	(closest_city, min_edge, min_edge_time) = (None, None, None)
	while len(queue) > 0:
		(_, current_city) = heapq.heappop(queue)
		if all([current_city not in visited, current_city in end_cities]):
			closest_city = current_city
			(min_edge, min_edge_time) = min(paths[current_city], key=itemgetter(1))
			break
		visited.add(current_city)
		for candidate in citymap[current_city]:
			(city_candidate, time_candidate) = candidate
			if city_candidate in visited:
				continue
			new_time = time[current_city] + time_candidate
			if city_candidate in time and time[city_candidate] <= new_time:
				continue
			time[city_candidate] = new_time
			paths[city_candidate] = paths[current_city] + [((current_city, city_candidate), time_candidate)]
			heapq.heappush(queue, (time[city_candidate], city_candidate))
	return (closest_city, min_edge, min_edge_time)
(num_of_cities, num_of_machines) = map(int, input().strip().split(' '))
if num_of_machines == num_of_cities:
	total_time_to_destroy = 0
	for i in range(num_of_cities - 1):
		(city_from, city_to, time) = map(int, input().strip().split(' '))
		total_time_to_destroy += time
	print(total_time_to_destroy)
	sys.exit(0)
citymap = defaultdict(set)
for i in range(num_of_cities - 1):
	(city_from, city_to, time) = map(int, input().strip().split(' '))
	citymap[city_from].add((city_to, time))
	citymap[city_to].add((city_from, time))
if num_of_machines == 1:
	city_with_machine = int(input().strip())
	total_time_to_destroy = sum([c[1] for c in citymap[city_with_machine]])
	print(total_time_to_destroy)
	sys.exit(0)
cities_with_machines = set()
for i in range(num_of_machines):
	city_with_machine = int(input().strip())
	cities_with_machines.add(city_with_machine)
total_total_time_to_destroy = 0
while len(cities_with_machines) > 0:
	city_with_machine = cities_with_machines.pop()
	(city, edge_to_destroy, edge_time) = find_city_to_disconnect(city_with_machine, cities_with_machines, citymap)
	if city is None:
		cities_with_machines -= set([city_with_machine])
		continue
	cities_with_machines.add(city_with_machine)
	total_total_time_to_destroy += edge_time
	(start_city_edge, end_city_edge) = edge_to_destroy
	citymap[start_city_edge] -= set([(end_city_edge, edge_time)])
	citymap[end_city_edge] -= set([(start_city_edge, edge_time)])
print(total_total_time_to_destroy)


class Graph:

	def __init__(self, vertices):
		self.nodes = vertices
		self.parent = {x: x for x in range(vertices)}
		self.rank = {x: 0 for x in range(vertices)}
		self.robots = {x: False for x in range(vertices)}
		self.edges = []

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

	def union(self, element1, element2, check):
		parent1 = self.find(element1)
		parent2 = self.find(element2)
		if self.rank[parent1] < self.rank[parent2]:
			self.parent[parent1] = parent2
		elif self.rank[parent1] > self.rank[parent2]:
			self.parent[parent2] = parent1
		else:
			self.parent[parent2] = parent1
			self.rank[parent1] += 1
		if check:
			self.robots[parent1] = True
			self.robots[parent2] = True

	def matrix(self):
		store = 0
		self.edges = sorted(self.edges, reverse=True)
		for x in self.edges:
			(weight, source, destination) = (x[0], x[1], x[2])
			parent1 = self.find(source)
			parent2 = self.find(destination)
			if self.robots[parent1] and self.robots[parent2]:
				store += weight
				continue
			if self.robots[parent1] or self.robots[parent2]:
				self.union(source, destination, True)
			if not self.robots[parent1] and (not self.robots[parent2]):
				self.union(source, destination, False)
		print(store)
(vertices, robots) = map(int, input().split())
g = Graph(vertices)
for x in range(vertices - 1):
	(source, destination, weight) = map(int, input().split())
	g.edges.append([weight, source, destination])
for x in range(robots):
	y = int(input())
	g.robots[y] = True
g.matrix()


from collections import defaultdict
import sys
sys.setrecursionlimit(10000)

class UnionFind:

	def __init__(self):
		self.leaders = defaultdict(lambda : None)
		self.robots = defaultdict(bool)

	def find(self, x, r=False):
		l = self.leaders.get(x, x)
		if l != x:
			l = self.find(l, r)
		if r:
			self.robots[l] = True
		return l

	def union(self, x, y):
		(lx, ly) = (self.find(x), self.find(y))
		if lx != ly:
			self.leaders[lx] = ly
			self.robots[ly] |= self.robots[lx]
uf = UnionFind()
(n, r) = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(n - 1)]
robots = set((int(input()) for _ in range(r)))
result = 0
for (a, b, c) in sorted(edges, key=lambda e: -e[2]):
	la = uf.find(a, a in robots)
	lb = uf.find(b, b in robots)
	if not (uf.robots[la] and uf.robots[lb]):
		uf.union(a, b)
	else:
		result += c
print(result)


def findset(u, mapping):
	return mapping[u]

def union(u, v, mapping, counts):
	if len(counts[u]) < len(counts[v]):
		for x in counts[u]:
			counts[v].append(x)
			mapping[x] = v
		del counts[u]
	else:
		for x in counts[v]:
			counts[u].append(x)
			mapping[x] = u
		del counts[v]

def solve(roads, machines):
	roads = sorted(roads, key=lambda road: road[2], reverse=True)
	mapping = {}
	visited = set()
	counts = {}
	total = 0
	for road in roads:
		(u, v, c) = road
		if mapping.get(u) == None:
			mapping[u] = u
			counts[u] = [u]
		if mapping.get(v) == None:
			mapping[v] = v
			counts[v] = [v]
		if u in machines:
			visited.add(findset(u, mapping))
		if v in machines:
			visited.add(findset(v, mapping))
		if findset(u, mapping) in visited and findset(v, mapping) in visited:
			total += c
		elif findset(u, mapping) not in visited and findset(v, mapping) not in visited:
			union(findset(u, mapping), findset(v, mapping), mapping, counts)
		else:
			if findset(u, mapping) in visited:
				visited.remove(findset(u, mapping))
			if findset(v, mapping) in visited:
				visited.remove(findset(v, mapping))
			union(findset(u, mapping), findset(v, mapping), mapping, counts)
			visited.add(findset(u, mapping))
	return total
(n, m) = [int(x) for x in input().strip().split(' ')]
roads = [[int(x) for x in input().strip().split(' ')] for i in range(n - 1)]
machines = [int(input()) for i in range(m)]
machines = set(machines)
print(solve(roads, machines))


(n, k) = (int(x) for x in input().split())
nbrs = [[] for i in range(n)]
for _ in range(n - 1):
	(a, b, wt) = (int(x) for x in input().split())
	nbrs[a].append((b, wt))
	nbrs[b].append((a, wt))
rank = [-1 for i in range(n)]
parent = [-1 for i in range(n)]
up_cost = [-1 for i in range(n)]
rank[0] = 0
parent[0] = 0
up_cost[0] = 0
stack = [0]
while len(stack) > 0:
	a = stack.pop(0)
	for (b, wt) in nbrs[a]:
		if rank[b] != -1:
			continue
		rank[b] = rank[a] + 1
		parent[b] = a
		up_cost[b] = wt
		stack.append(b)
order = sorted([(rank[a], a) for a in range(n)], reverse=True)
state = [(0, 0) for i in range(n)]
for _ in range(k):
	a = int(input())
	state[a] = (1, up_cost[a])
total = 0
for (_, a) in order:
	(mach, cost) = state[a]
	if mach == 1:
		for (b, wt) in nbrs[a]:
			if parent[a] == b:
				continue
			if state[b][0] == 1:
				total += state[b][1]
	else:
		x = [0]
		for (b, wt) in nbrs[a]:
			if parent[a] == b:
				continue
			if state[b][0] == 0:
				continue
			x.append(state[b][1])
		v = min(up_cost[a], max(x))
		state[a] = (1, v)
		total += sum(x) - max(x)
print(total)


class Node:

	def __init__(self, id):
		(self.id, self.m, self.gid) = (id, 0, id)

class Edage:

	def __init__(self, a, b, w):
		(self.a, self.b, self.w) = (a, b, w)
(n, k) = map(int, input().split(' '))
nodes = [Node(i) for i in range(n)]
(es, gc, rs) = ([None] * (n - 1), n, 0)
for i in range(n - 1):
	(a, b, w) = map(int, input().split(' '))
	e = Edage(nodes[a], nodes[b], w)
	es[i] = e
es.sort(key=lambda x: -x.w)
for _ in range(k):
	nodes[int(input())].m = 1

def getGroupId(x):
	t = x
	while t.gid != t.id:
		t = nodes[t.gid]
	while x.gid != t.id:
		v = x.gid
		x.gid = t.id
		x = nodes[v]
	return t.id

def megerGroup(x, y):
	if x.gid < y.gid:
		x.gid = y.gid
	else:
		y.gid = x.gid
	(x.m, y.m) = (x.m + y.m, x.m + y.m)
for e in es:
	ga = nodes[getGroupId(e.a)]
	gb = nodes[getGroupId(e.b)]
	if ga != gb:
		if ga.m and gb.m:
			rs += e.w
			continue
		else:
			megerGroup(ga, gb)
print(rs)


import math
import os
import random
import re
import sys

def minTime(n, roads, machines):
	co = 0
	machset = [False] * n
	for i in machines:
		machset[i] = True
	roads.sort(key=lambda x: x[2], reverse=True)
	arr = [-1 for i in range(n)]
	for i in roads:
		pz = parent(arr, i[0])
		po = parent(arr, i[1])
		if machset[pz] and machset[po]:
			co += i[2]
		elif machset[pz]:
			union(arr, i[0], i[1])
		elif machset[po]:
			union(arr, i[1], i[0])
		else:
			union(arr, i[0], i[1])
	return co

def parent(arr, i):
	p = i
	while arr[p] >= 0:
		p = arr[p]
	x = i
	while arr[x] >= 0:
		t = x
		x = arr[x]
		arr[t] = p
	return p

def union(arr, i, j):
	x = arr[parent(arr, j)]
	arr[parent(arr, j)] = parent(arr, i)
	arr[parent(arr, i)] += x
nk = input().split()
n = int(nk[0])
k = int(nk[1])
roads = []
for _ in range(n - 1):
	roads.append(list(map(int, input().rstrip().split())))
machines = []
for _ in range(k):
	machines_item = int(input())
	machines.append(machines_item)
result = minTime(n, roads, machines)
print(result)


import math
import os
import random
import re
import sys
from math import inf

def doom_time(root_tree, colors, weights):
	(a, w) = _doom_time(root_tree, colors, weights)
	return a

def _doom_time(root_tree, colors, weights):
	value = root_tree['value']
	cinfo = [_doom_time(v, colors, weights) for v in root_tree['children']]
	edges = [weights[value, v['value']] for v in root_tree['children']]
	kappas = [min(r, w) for (r, (a, w)) in zip(edges, cinfo)]
	sumalphas = sum((a for (a, _) in cinfo))
	if colors[value] == 'red':
		w = inf
		alpha = sumalphas + sum(kappas)
	else:
		w = max(kappas) if kappas else 0
		alpha = sumalphas + sum(kappas) - w
	return (alpha, w)

def edges2graph(n, edges):
	graph = {i: set() for i in range(n)}
	weights = dict()
	for (a, b, w) in edges:
		graph[a].add(b)
		graph[b].add(a)
		weights[a, b] = w
		weights[b, a] = w
	return (graph, weights)

def graph2tree(graph, root, parent):
	node = {'value': root, 'children': [graph2tree(graph, v, root) for v in graph[root] if v != parent]}
	return node
(n, k) = map(int, input().split())
roads = []
for _ in range(n - 1):
	roads.append(list(map(int, input().rstrip().split())))
colors = {i: 'blue' for i in range(n)}
for _ in range(k):
	colors[int(input())] = 'red'
(graph, weights) = edges2graph(n, roads)
tree = graph2tree(graph, 0, -1)
print(doom_time(tree, colors, weights))


(n, k) = map(int, input().split())
e = sorted((tuple(map(int, input().split())) for _ in range(1, n)), key=lambda x: x[::-1], reverse=True)
g = [-1] * n

def root(x):
	if g[x] < 0:
		return x
	g[x] = root(g[x])
	return g[x]
h = [False] * n

def union(x, y):
	if g[x] < g[y]:
		(x, y) = (y, x)
	g[y] += g[x]
	g[x] = y
	h[y] = h[y] or h[x]
for _ in range(k):
	h[int(input())] = True
r = 0
for (u, v, c) in e:
	u = root(u)
	v = root(v)
	if h[u] and h[v]:
		r += c
	else:
		union(u, v)
print(r)


import math
import os
import random
import re
import sys

class Matrix:
	MACHINE = 'MACHINE'

	def __init__(self, roads, num_cities, machines):
		self.roads = roads
		self.num_cities = num_cities
		self.machines = machines
		self.sets = [[city] for city in range(num_cities)]
		self.set_member_lookup = {city: city for city in range(num_cities)}
		self.mark_cities_with_machines(machines)

	def mark_cities_with_machines(self, machines):
		for machine in machines:
			city_with_machine = self.find_set(machine)
			city_with_machine.append(self.MACHINE)

	def find_set(self, city):
		set_i = self.set_member_lookup[city]
		return self.sets[set_i]

	def union(self, set_a, set_b, city_a):
		if set_a is not None and set_b is not None:
			set_a.extend(set_b)
			set_a_index = self.set_member_lookup[city_a]
			for city in set_b:
				self.set_member_lookup[city] = set_a_index
			set_b = None

	def min_time(self):
		total_time = 0
		descending_roads = list(reversed(sorted(self.roads, key=lambda tuple: tuple[2])))
		for road in descending_roads:
			(city_a, city_b, time_to_destroy) = road
			set_a = self.find_set(city_a)
			set_b = self.find_set(city_b)
			if self.MACHINE in set_a and self.MACHINE in set_b:
				total_time += time_to_destroy
			else:
				self.union(set_a, set_b, city_a)
		return total_time
(num_cities, num_machines) = map(int, input().split())
roads = []
for _ in range(num_cities - 1):
	roads.append(tuple(map(int, input().rstrip().split())))
machines = []
for _ in range(num_machines):
	machines.append(int(input()))
matrix = Matrix(roads, num_cities, machines)
print(matrix.min_time())