Byteland has $N$ cities (numbered from $\mbox{1}$ to $N$) and $N-1$ bidirectional roads. It is guaranteed that there is a route from any city to any other city. 

Jeanie is a postal worker who must deliver $\mbox{K}$ letters to various cities in Byteland. She can start and end her delivery route in any city. Given the destination cities for $\mbox{K}$ letters and the definition of each road in Byteland, find and print the minimum distance Jeanie must travel to deliver all $\mbox{K}$ letters.

Note: The letters can be delivered in any order.

Input Format

The first line contains two space-separated integers, $N$ (the number of cities) and $\mbox{K}$ (the number of letters), respectively. 

The second line contains $\mbox{K}$ space-separated integers describing the delivery city for each letter. 

Each line $\boldsymbol{i}$ of the $N-1$ subsequent lines contains $3$ space-separated integers describing a road as $u_iv_i d_i$, where $d_i$ is the distance (length) of the bidirectional road between cities $u_i$ and $v_i$.

Constraints

$2\leq K\leq N\leq10^5$
$1\leq d_i\leq10^3$
$\textit{Byteland is a weighted undirected acyclic graph.}$

Output Format

Print the minimum distance Jeanie must travel to deliver all $\mbox{K}$ letters.

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

Sample Output 0
6

Explanation 0

Jeanie has $3$ letters she must deliver to cities $\mbox{I}$, $3$, and $\begin{array}{c}A\end{array}$ in the following map of Byteland:

One of Jeanie's optimal routes is $\underbrace{3\to2}_{2}\overbrace{\to1}^{1}\underbrace{\to2}_{1}\overbrace{\to4}^{2}_{\cdot}$, for a total distanced traveled of $2+1+1+2=6$. Thus, we print $\boldsymbol{6}$ on a new line.

Difficulty: MEDIUM
Tags: Graph algorithms

Starter code:

Solutions:
[n, k] = list(map(int, input().split(' ')))
cities = set(map(int, input().split(' ')))

def log(*args):
	if False:
		print(*args)
counts = dict()
edges = dict()
for i in range(n):
	edges[i + 1] = dict()
total = 0
for _ in range(n - 1):
	[u, v, d] = list(map(int, input().split(' ')))
	counts[u] = counts.get(u, 0) + 1
	counts[v] = counts.get(v, 0) + 1
	edges[u][v] = d
	edges[v][u] = d
	total += d
leaves = []
for (u, count) in counts.items():
	if count == 1:
		leaves.append(u)
log(edges, counts, leaves, total)
while len(leaves):
	leaf = leaves.pop()
	if leaf in cities:
		log('ignoring city', leaf)
		continue
	log('must trim', leaf)
	other = list(edges[leaf].keys())[0]
	d = edges[other][leaf]
	total -= d
	del edges[other][leaf]
	del edges[leaf]
	if len(list(edges[other].keys())) == 1:
		leaves.append(other)
	log('new leaves', leaves)
parents = dict()
cur = list(cities)[0]
index = 0
stack = [cur]
indices = []
order = []
while True:
	log('set', cur, index, stack, indices)
	items = list(edges[cur].keys())
	log('children', items)
	if index == len(items):
		parent = parents.get(cur)
		log('order', cur, parent)
		order.append((cur, parent))
		stack.pop()
		if len(stack) == 0:
			break
		index = indices.pop() + 1
		cur = parent
	else:
		child = items[index]
		if child == parents.get(cur):
			index += 1
			continue
		parents[child] = cur
		cur = child
		indices.append(index)
		index = 0
		stack.append(child)
longest_path_cache = dict()
for (city, parent) in order:
	inner = 0
	to = 0
	tos = []
	inners = []
	for (other, d) in edges[city].items():
		if other == parent:
			continue
		(o_inner, o_to) = longest_path_cache[other]
		inners.append(o_inner)
		if o_inner > inner:
			inner = o_inner
		tos.append(o_to + d)
		if o_to + d > to:
			to = o_to + d
	my_inner = 0
	if len(tos) > 1:
		tos.sort()
		my_inner = tos[len(tos) - 1] + tos[len(tos) - 2]
	longest_path_cache[city] = (max(inner, my_inner), to)
(inner, _) = longest_path_cache[list(cities)[0]]
log('best inner', inner)
log(edges, counts, leaves, total)
print(total * 2 - inner)


def idfs(g, dt, ndt, cts):

	def _dfs(root, visited, niter):
		dfstack = [[root, 0, -1, root in cts, 0, 0]]
		retstack = []
		while dfstack:
			[node, i, c, fnd, d, maxd] = dfstack[-1]
			if c == -1:
				visited[node] = niter
				dfstack[-1][2] = 0
			elif c == 0:
				if i < len(g[node]):
					(neigh, dist) = g[node][i]
					if visited[neigh] < niter:
						if dt[node][i] is None:
							dfstack[-1][2] = 3
							dfstack.append([neigh, 0, -1, neigh in cts, 0, 0])
							continue
						else:
							dfstack[-1][2] = 1
					else:
						dfstack[-1][2] = 4
				else:
					dfstack[-1][2] = 2
			elif c == 3:
				(dt[node][i], ndt[node][i]) = retstack.pop()
				dfstack[-1][2] = 1
			elif c == 1:
				dfstack[-1][2] = 4
				if dt[node][i] < 0:
					continue
				(neigh, dist) = g[node][i]
				fnd |= True
				d += 2 * dist + dt[node][i]
				maxd = max(2 * dist + dt[node][i] - (dist + ndt[node][i]), maxd)
				dfstack[-1][3] = fnd
				dfstack[-1][4] = d
				dfstack[-1][5] = maxd
			elif c == 4:
				dfstack[-1][1] += 1
				dfstack[-1][2] = 0
			elif c == 2:
				retstack.append((d, d - maxd) if fnd else (-1, -1))
				dfstack.pop()
		return retstack[0]
	res = 1 << 63
	visited = [0] * len(g)
	for (i, c) in enumerate(cts):
		(_, d) = _dfs(c, visited, i + 1)
		res = min(res, d)
	return res
[n, k] = [int(x) for x in input().split()]
cts = set((int(x) - 1 for x in input().split()))
g = [[] for i in range(n)]
for i in range(n - 1):
	[u, v, d] = [int(x) for x in input().split()]
	g[u - 1].append((v - 1, d))
	g[v - 1].append((u - 1, d))
dt = [[None] * len(g[i]) for i in range(n)]
ndt = [[None] * len(g[i]) for i in range(n)]
res = idfs(g, dt, ndt, cts)
print(res)


import sys
sys.setrecursionlimit(100000)

def main():
	(N, K) = readints()
	targets = readints()
	targets = [t - 1 for t in targets]
	graph = Graph()
	for i in range(0, N):
		graph.insertVertex(i)
	for i in range(0, N - 1):
		(u, v, distance) = readints()
		u = u - 1
		v = v - 1
		edge = Edge(u, v, distance)
		graph.insertEdge(u, v, edge)
	discovered = {}
	start = targets[0]
	discovered[start] = None
	BFS(graph, start, discovered)
	visited = {}
	total_length = 0
	subgraph = Graph()
	for i in range(0, N):
		subgraph.insertVertex(i)
	for t in targets:
		e = discovered[t]
		while (e != None) & (e not in visited):
			visited[e] = True
			o = e.opposite(t)
			subgraph.insertEdge(o, t, Edge(o, t, e.weight()))
			total_length += e.weight()
			t = o
			e = discovered[o]
	diameters = {}
	Diameter(subgraph, start, diameters)
	max_diameter = max([a + b for (a, b) in diameters.values()])
	print(2 * total_length - max_diameter)

def readints():
	return [int(x) for x in input().split()]

class Edge:

	def __init__(self, u, v, d):
		self._u = u
		self._v = v
		self._distance = d

	def opposite(self, u):
		return self._v if u == self._u else self._u

	def weight(self):
		return self._distance

	def print(self):
		print(self._u, self._v, self._distance)

class Graph:

	def __init__(self, directed=False):
		self._outgoing = {}
		self._incoming = {} if directed else self._outgoing

	def insertVertex(self, index):
		self._outgoing[index] = {}
		self._incoming[index] = {}

	def insertEdge(self, u, v, edge):
		if v not in self._outgoing[u]:
			self._outgoing[u][v] = edge
			self._incoming[v][u] = edge
		else:
			old_edge = self._outgoing[u][v]
			if edge.weight() < old_edge.weight():
				self._outgoing[u][v] = edge
				self._incoming[v][u] = edge

	def incident_edges(self, v, outgoing=True):
		adj = self._outgoing if outgoing else self._incoming
		for edge in adj[v].values():
			yield edge

def BFS(g, s, discovered):
	level = [s]
	while len(level) > 0:
		next_level = []
		for u in level:
			for e in g.incident_edges(u):
				v = e.opposite(u)
				if v not in discovered:
					discovered[v] = e
					next_level.append(v)
		level = next_level

def Diameter(g, s, diameters):
	child_edges = [e for e in g.incident_edges(s) if e._u == s]
	if len(child_edges) == 0:
		diameters[s] = (0, 0)
	elif len(child_edges) == 1:
		u = child_edges[0].opposite(s)
		diameters[s] = (max(Diameter(g, u, diameters)) + child_edges[0].weight(), 0)
	else:
		max_options = [max(Diameter(g, e.opposite(s), diameters)) + e.weight() for e in child_edges]
		diameters[s] = (max(max_options), second_max(max_options))
	return diameters[s]

def second_max(numbers):
	count = 0
	m1 = m2 = float('-inf')
	for x in numbers:
		count += 1
		if x > m2:
			if x >= m1:
				(m1, m2) = (x, m1)
			else:
				m2 = x
	return m2 if count >= 2 else None
main()


[n, k] = list(map(int, input().split(' ')))
cities = set(map(int, input().split(' ')))

def log(*args):
	if False:
		print(*args)
counts = dict()
edges = dict()
for i in range(n):
	edges[i + 1] = dict()
total = 0
for _ in range(n - 1):
	[u, v, d] = list(map(int, input().split(' ')))
	counts[u] = counts.get(u, 0) + 1
	counts[v] = counts.get(v, 0) + 1
	edges[u][v] = d
	edges[v][u] = d
	total += d
leaves = []
for (u, count) in counts.items():
	if count == 1:
		leaves.append(u)
log(edges, counts, leaves, total)
while len(leaves):
	leaf = leaves.pop()
	if leaf in cities:
		log('ignoring city', leaf)
		continue
	log('must trim', leaf)
	other = list(edges[leaf].keys())[0]
	d = edges[other][leaf]
	total -= d
	del edges[other][leaf]
	del edges[leaf]
	if len(list(edges[other].keys())) == 1:
		leaves.append(other)
	log('new leaves', leaves)
parents = dict()
cur = list(cities)[0]
index = 0
stack = [cur]
indices = []
order = []
while True:
	log('set', cur, index, stack, indices)
	items = list(edges[cur].keys())
	log('children', items)
	if index == len(items):
		parent = parents.get(cur)
		log('order', cur, parent)
		order.append((cur, parent))
		stack.pop()
		if len(stack) == 0:
			break
		index = indices.pop() + 1
		cur = parent
	else:
		child = items[index]
		if child == parents.get(cur):
			index += 1
			continue
		parents[child] = cur
		cur = child
		indices.append(index)
		index = 0
		stack.append(child)
longest_path_cache = dict()
for (city, parent) in order:
	inner = 0
	to = 0
	tos = []
	inners = []
	for (other, d) in edges[city].items():
		if other == parent:
			continue
		(o_inner, o_to) = longest_path_cache[other]
		inners.append(o_inner)
		if o_inner > inner:
			inner = o_inner
		tos.append(o_to + d)
		if o_to + d > to:
			to = o_to + d
	my_inner = 0
	if len(tos) > 1:
		tos.sort()
		my_inner = tos[len(tos) - 1] + tos[len(tos) - 2]
	longest_path_cache[city] = (max(inner, my_inner), to)
(inner, _) = longest_path_cache[list(cities)[0]]
log('best inner', inner)
log(edges, counts, leaves, total)
print(total * 2 - inner)


import collections
import queue
(n, k) = [int(p) for p in input().strip().split()]
cities = set([int(p) for p in input().strip().split()])
graph = dict(((i, []) for i in range(1, n + 1)))
for j in range(n - 1):
	(x, y, d) = [int(p) for p in input().strip().split()]
	graph[x].append((y, d))
	graph[y].append((x, d))

def solve(root):
	level = 1
	q = queue.Queue()
	q.put((root, level, None, 0))
	seen = set([])
	levels = collections.defaultdict(set)
	tree = {}
	while not q.empty():
		(item, level, parent, up) = q.get()
		levels[level].add(item)
		seen.add(item)
		tree[item] = dict(id=item, parent=parent, level=level, children=set([]), up=up)
		for neigh in graph[item]:
			(child, d) = neigh
			if child not in seen:
				q.put((child, level + 1, item, d))
				seen.add(child)
				tree[item]['children'].add(child)
	top = 0
	for level in sorted(levels.keys(), reverse=True):
		for item in levels[level]:
			if not tree[item]['children']:
				if item in cities:
					tree[item]['md'] = 0
					tree[item]['td'] = 0
				else:
					parent = tree[item]['parent']
					tree[parent]['children'].remove(item)
			else:
				distances = []
				total_distance = 0
				for child in tree[item]['children']:
					d = tree[child]['up'] + tree[child]['md']
					distances.append(d)
					td = tree[child]['up'] * 2 + tree[child]['td']
					total_distance += td
				distances.sort()
				tree[item]['md'] = distances[-1]
				tree[item]['td'] = total_distance
				top = max(top, sum(distances[-2:]))
	return tree[root]['td'] - top
res = solve(next((r for r in cities)))
print(res)


(n, k) = map(int, input().split(' '))
delivery = [False for i in range(n)]
indeg = [0 for i in range(n)]
for i in map(int, input().split(' ')):
	delivery[i - 1] = True
adj = [[] for i in range(n)]
u = [0 for i in range(n - 1)]
v = [0 for i in range(n - 1)]
w = [0 for i in range(n - 1)]
for i in range(n - 1):
	(u[i], v[i], w[i]) = map(int, input().split(' '))
	u[i] -= 1
	v[i] -= 1
	adj[u[i]].append((v[i], i))
	adj[v[i]].append((u[i], i))
	indeg[u[i]] += 1
	indeg[v[i]] += 1
queue = []
head = 0
tail = 0
for i in range(n):
	if indeg[i] == 1:
		queue.append(i)
		tail += 1
still_exist = [True for i in range(n - 1)]
while head < tail:
	h = queue[head]
	head += 1
	if delivery[h]:
		continue
	for (t, p) in adj[h]:
		indeg[t] -= 1
		still_exist[p] = False
		if indeg[t] == 1:
			queue.append(t)
			tail += 1
adj = [[] for i in range(n)]
sum = 0
for i in range(n - 1):
	if still_exist[i]:
		adj[u[i]].append((v[i], w[i]))
		adj[v[i]].append((u[i], w[i]))
		sum += w[i]
ans = sum * 2

def bfs(s):
	dist = [-1 for i in range(n)]
	dist[s] = 0
	queue = [s]
	head = 0
	tail = 1
	while head < tail:
		u = queue[head]
		head += 1
		for (v, w) in adj[u]:
			if dist[v] == -1:
				dist[v] = dist[u] + w
				queue.append(v)
				tail += 1
	mx = s
	for i in range(n):
		if dist[i] > dist[mx]:
			mx = i
	return (mx, dist[mx])
for i in range(n):
	if len(adj[i]) > 0:
		(u, _) = bfs(i)
		break
(_, d) = bfs(u)
print(ans - d)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


import sys
sys.setrecursionlimit(100000)
(n, k) = [int(x) for x in input().split()]
must_visit = set([int(x) - 1 for x in input().split()])
edges = [dict() for x in range(n)]
edge_total = 0
for _ in range(n - 1):
	(u, v, d) = [int(x) for x in input().split()]
	edges[u - 1][v - 1] = d
	edges[v - 1][u - 1] = d
	edge_total += d
leaves = []
for node in range(n):
	if len(edges[node]) == 1:
		leaves.append(node)
while leaves:
	cur = leaves.pop()
	if cur not in must_visit:
		for key in edges[cur]:
			nxt = key
		edge_total -= edges[nxt][cur]
		del edges[nxt][cur]
		if len(edges[nxt]) == 1:
			leaves.append(nxt)
for node in range(n):
	if node in must_visit:
		a = node
		break

def pathfinder(node, parent=None):
	paths = []
	for neighbor in edges[node]:
		if neighbor != parent:
			paths.append(pathfinder(neighbor, node))
			paths[-1][0] += edges[node][neighbor]
	return max(paths) if paths else [0, node]
(_, b) = pathfinder(a)
(longest_path, _) = pathfinder(b)
print(edge_total * 2 - longest_path)


import sys
sys.setrecursionlimit(100000)
from collections import deque
(N, K) = map(int, input().split(' '))
K = set()
for k in map(int, input().split(' ')):
	K.add(k - 1)
G = [{} for _ in range(N)]
for _ in range(N - 1):
	(u, v, d) = map(int, input().split(' '))
	G[u - 1][v - 1] = d
	G[v - 1][u - 1] = d
queue = deque()
for u in range(N):
	if len(G[u]) == 1 and (not u in K):
		queue.append(u)
while queue:
	u = queue.popleft()
	for v in list(G[u].keys()):
		del G[u][v]
	del G[v][u]
	if len(G[v]) == 1 and (not v in K):
		queue.append(v)

def dfs(G, V, u):
	V[u] = True
	(distVal, sumVal, maxVal1, maxVal2) = (0, 0, 0, 0)
	for (v, d) in G[u].items():
		if V[v]:
			continue
		(distValv, sumValv, maxValv) = dfs(G, V, v)
		distVal += d + distValv
		if d + maxValv > maxVal1:
			(maxVal1, maxVal2) = (d + maxValv, maxVal1)
		elif d + maxValv > maxVal2:
			maxVal2 = d + maxValv
		sumVal = max(sumVal, sumValv)
	sumVal = max(sumVal, maxVal1 + maxVal2)
	return (distVal, sumVal, maxVal1)
V = [False] * N
for k in K:
	if len(G[k]) > 1:
		continue
	(distVal, sumVal, maxVal) = dfs(G, V, k)
	print(2 * distVal - sumVal)
	break


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


(N, K) = map(int, input().split())
letters = [int(x) for x in input().split()]
graph = dict(((i, {}) for i in range(1, N + 1)))
for i in range(N - 1):
	(u, v, d) = map(int, input().split())
	graph[u][v] = d
	graph[v][u] = d
active = [letters[0]]
totalDist = 0
longest = 0
parent = [0] * (N + 1)
depth = [-1] * (N + 1)
mustVisit = [False] * (N + 1)
for i in letters:
	mustVisit[i] = True
while active:
	node = active[-1]
	if depth[node] < 0:
		depth[node] = 0
		for child in graph[node]:
			if child == parent[node]:
				continue
			parent[child] = node
			active.append(child)
	else:
		active.pop()
		depth1 = 0
		depth2 = 0
		for child in graph[node]:
			if child == parent[node]:
				continue
			if mustVisit[child]:
				mustVisit[node] = True
				totalDist += graph[node][child]
				d = depth[child] + graph[node][child]
				if d > depth1:
					depth2 = depth1
					depth1 = d
				elif d > depth2:
					depth2 = d
		depth[node] = depth1
		if depth1 + depth2 > longest:
			longest = depth1 + depth2
print(2 * totalDist - longest)


def lstin():
	return list(map(int, input().strip().split()))

def dfs(edges, root):
	stack = [(root, v) for (v, d) in edges[root]]
	flatten = list()
	while stack:
		(u, v) = stack.pop()
		flatten.append((u, v))
		stack.extend(((v, w) for (w, d) in edges[v] if w != u))
	flatten.reverse()
	return flatten

def get_subtree(edges, is_goal, root):
	subt = is_goal[:]
	for (u, v) in dfs(edges, root):
		subt[u] = subt[u] or subt[v]
	return subt

def get_farthest(edges, is_goal, subtree, root):
	visited = [False for _ in edges]
	st = [(0, root)]
	visited[root] = True
	mx = (0, root)
	dist_all = 0
	while st:
		(dist, u) = st.pop()
		for (v, d) in edges[u]:
			if not visited[v] and subtree[v]:
				elm = (dist + d, v)
				dist_all += d
				if is_goal[v]:
					mx = max(mx, elm)
				st.append(elm)
				visited[v] = True
	return (dist_all, mx)
(N, K) = lstin()
goals = lstin()
is_goal = [False] * (N + 1)
for u in goals:
	is_goal[u] = True
edges = [list() for _ in range(N + 1)]
for _ in range(N - 1):
	(u, v, d) = lstin()
	edges[u].append((v, d))
	edges[v].append((u, d))
subtree = get_subtree(edges, is_goal, goals[0])
(_, (_, u)) = get_farthest(edges, is_goal, subtree, goals[0])
(D, (d, _)) = get_farthest(edges, is_goal, subtree, u)
print(2 * D - d)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


import sys

def solve(g, cc):

	def walk_gen(gr, node):
		marked = set()

		def gen(gr, node):
			stack = [(node, None, None, 0)]
			while stack:
				(node, parent, distance, index) = stack.pop()
				marked.add(node)
				yield (parent, node, distance)
				if index != len(gr[node]) - 1:
					stack.append((node, parent, distance, index + 1))
				i = index
				while i != len(gr[node]):
					(child, child_distance) = gr[node][i]
					if child not in marked:
						stack.append((child, node, child_distance, 0))
						break
					i += 1
		yield from gen(gr, node)

	def get_subgraph():
		cache = set(cc)
		sg = {}
		for (fr, to, distance) in walk_gen(g, min(cc)):
			if to in cache:
				cache.add(to)
				if fr is None:
					if to not in sg:
						sg[to] = []
				else:
					cache.add(fr)
					for (u, v) in ((fr, to), (to, fr)):
						if u in sg:
							sg[u].append((v, distance))
						else:
							sg[u] = [(v, distance)]
		new_sg = {n: [] for n in sg}
		for n in sg:
			st = dict()
			for (u, v) in sg[n]:
				st[u] = v
			new_sg[n] = [(u, v) for (u, v) in st.items()]
		return new_sg

	def path_gen(gr, node):
		stack = [(node, 0)]
		marked = set()
		while stack:
			(fr, distance) = stack.pop()
			yield (fr, distance)
			marked.add(fr)
			cnt = 0
			for (child, d) in gr[fr].items():
				if child not in marked:
					stack.append((child, distance + d))
					cnt += 1

	def max_path_bf(gr):
		mx = 0
		for (n, arcs) in gr.items():
			if len(arcs) < 2:
				for (c, d) in path_gen(gr, n):
					mx = max(mx, d)
		return mx

	def double_total_sum(gr):
		sm = 0
		for (n, archs) in gr.items():
			for (_, d) in archs:
				sm += d
		return sm

	def max_path(gr):
		root = min(gr)
		cache = {n: 0 for n in gr}
		for (pr, ch, d) in walk_gen(gr, root):
			if d is not None:
				v = d + cache[ch]
				cache[pr] = max(cache[pr], v)
		print('cache=%s' % cache, file=sys.stderr)
		mx = cache[root]
		marked = set()
		stack = [root]
		while stack:
			node = stack.pop()
			marked.add(node)
			(cnt, first, second) = (0, 0, 0)
			for (ch, d) in gr[node]:
				if ch not in marked:
					stack.append(ch)
					cnt += 1
					v = d + cache[ch]
					if v >= first:
						(first, second) = (v, first)
					elif v > second:
						second = v
			diameter = 0
			if cnt == 1:
				diameter = first
			else:
				diameter = first + second
			mx = max(mx, diameter)
		return mx
	sg = get_subgraph()
	dts = double_total_sum(sg)
	mx = max_path(sg)
	return dts - mx
(n, k) = map(int, input().split())
cc = set(map(int, input().split()))
g = {i: list() for i in range(1, n + 1)}
for _ in range(n - 1):
	(fr, to, d) = map(int, input().split())
	g[fr].append((to, d))
	g[to].append((fr, d))
print(solve(g, cc))


import sys
(n, k) = map(int, sys.stdin.readline().split())
letters = [int(i) for i in sys.stdin.readline().split()]
graph = dict(((i, {}) for i in range(1, n + 1)))
for _ in range(n - 1):
	(u, v, cost) = map(int, sys.stdin.readline().split())
	graph[u][v] = cost
	graph[v][u] = cost
active = [letters[0]]
total_distance = 0
longest = 0
parent = [0] * (n + 1)
depth = [-1] * (n + 1)
need_to_visit = [False] * (n + 1)
for i in letters:
	need_to_visit[i] = True
while active:
	node = active[-1]
	if depth[node] < 0:
		depth[node] = 0
		for child in graph[node]:
			if child == parent[node]:
				continue
			parent[child] = node
			active.append(child)
	else:
		active.pop()
		depth1 = 0
		depth2 = 0
		for child in graph[node]:
			if child == parent[node]:
				continue
			if need_to_visit[child]:
				need_to_visit[node] = True
				total_distance += 2 * graph[node][child]
				d = depth[child] + graph[node][child]
				if d > depth1:
					depth2 = depth1
					depth1 = d
				elif d > depth2:
					depth2 = d
		depth[node] = depth1
		if depth1 + depth2 > longest:
			longest = depth1 + depth2
print(total_distance - longest)


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

def get_list():
	return [int(x) for x in input().strip().split(' ')]
(N, K) = get_list()
cities = set(get_list())
graph = defaultdict(list)
used = set()

class Node:

	def __init__(self, ix, parent=None, cost=None):
		self.parent = parent
		self.cost = cost
		self.children = []
		self.is_dest = ix in cities
		self.ix = ix

	def __repr__(self):
		return str((self.ix, self.cost)) + '\n children: ' + str(self.children)

def build_tree(graph, u):
	used.add(u)
	u_node = Node(u)
	for (v, d) in graph[u]:
		if v not in used:
			v_node = build_tree(graph, v)
			v_node.parent = u_node
			v_node.cost = d
			u_node.children.append(v_node)
	return u_node

def compute(root):
	(first, second, best3) = (0, 0, 0)
	res_need_visiting = root.is_dest
	(res_loop_cost, res_one_cost, res_two_cost, res_three_cost) = (0, 0, 0, 0)
	cnt_to_visit = int(root.is_dest)
	some_two_cost = 0
	for child in root.children:
		(need_visiting, loop_cost, one_cost, two_cost, three_cost) = compute(child)
		if need_visiting:
			some_two_cost = two_cost
			cnt_to_visit += 1
			res_need_visiting = True
			res_loop_cost += 2 * child.cost + loop_cost
			one_way_cost = loop_cost - one_cost + child.cost
			if one_way_cost > first:
				(second, first) = (first, one_way_cost)
			elif one_way_cost > second:
				second = one_way_cost
			delta3 = loop_cost - three_cost
			if delta3 > best3:
				best3 = delta3
	res_one_cost = res_loop_cost - first
	res_three_cost = res_loop_cost - best3
	if cnt_to_visit == 1:
		res_two_cost = some_two_cost
	else:
		res_two_cost = res_loop_cost - first - second
		res_three_cost = min(res_three_cost, res_two_cost)
	res_two_cost = min(res_two_cost, res_one_cost)
	res_two_cost = min(res_two_cost, res_three_cost)
	return (res_need_visiting, res_loop_cost, res_one_cost, res_two_cost, res_three_cost)
for _ in range(N - 1):
	(u, v, d) = get_list()
	graph[u].append((v, d))
	graph[v].append((u, d))
root = build_tree(graph, 1)
(res_need_visiting, res_loop_cost, res_one_cost, res_two_cost, _) = compute(root)
print(res_two_cost)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


(N, K) = map(int, input().split())
T = list(map(int, input().split()))
edges = [[] for i in range(N)]
for _ in range(N - 1):
	(A, B, C) = map(int, input().split())
	A -= 1
	B -= 1
	edges[A].append((B, C))
	edges[B].append((A, C))
needed = [0 for i in range(N)]
for val in T:
	needed[val - 1] = 1
q = [T[0] - 1]
covered = [0 for i in range(N)]
ind = 0
while ind < len(q):
	node = q[ind]
	covered[node] = 1
	for (neigh, _) in edges[node]:
		if covered[neigh] == 0:
			q.append(neigh)
	ind += 1
for i in range(len(q) - 1, -1, -1):
	node = q[i]
	covered[node] = 0
	for (neigh, _) in edges[node]:
		if covered[neigh] == 0:
			needed[node] = max(needed[node], needed[neigh])
for i in range(N):
	if needed[i] == 0:
		for (neigh, c) in edges[i]:
			edges[neigh].remove((i, c))
		edges[i] = []
ts = 0
for i in range(N):
	for (_, c) in edges[i]:
		ts += c
q = [(0, T[0] - 1)]
covered = [0 for i in range(N)]
ind = 0
while ind < len(q):
	(cost, node) = q[ind]
	covered[node] = 1
	for (neigh, c) in edges[node]:
		if covered[neigh] == 0:
			q.append((cost + c, neigh))
	ind += 1
q.sort()
(_, nextroot) = q[-1]
q = [(0, nextroot)]
covered = [0 for i in range(N)]
ind = 0
while ind < len(q):
	(cost, node) = q[ind]
	covered[node] = 1
	for (neigh, c) in edges[node]:
		if covered[neigh] == 0:
			q.append((cost + c, neigh))
	ind += 1
q.sort()
print(ts - q[-1][0])


def dfs(root, adj, nodes):
	parent = {root: None}
	depth = {root: 0}
	dist = {root: 0}
	stack = [root]
	while len(stack):
		curr = stack.pop()
		curr_depth = depth[curr]
		curr_dist = dist[curr]
		for nei in adj[curr]:
			if nei != parent[curr] and nei in nodes:
				parent[nei] = curr
				depth[nei] = curr_depth + 1
				dist[nei] = curr_dist + adj[curr][nei]
				stack.append(nei)
	return (parent, depth, dist)
(n, k) = map(int, input().split())
targets = set(map(int, input().split()))
nodes = set(range(1, n + 1))
adj = {x: dict() for x in nodes}
for _ in range(n - 1):
	(a, b, c) = map(int, input().split())
	adj[a][b] = c
	adj[b][a] = c
(parent, depth, dist) = dfs(list(targets)[0], adj, nodes)
nodes_sorted = sorted(nodes, key=lambda x: depth[x], reverse=True)
for node in nodes_sorted:
	num_connected = len([x for x in adj[node] if x in nodes])
	if node not in targets and num_connected == 1:
		nodes.remove(node)
		del adj[node]
furthest_node = max(nodes, key=lambda x: dist[x])
(parent, depth, dist) = dfs(furthest_node, adj, nodes)
furthest_node = max(nodes, key=lambda x: dist[x])
largest_distance = dist[furthest_node]
tot_sum = 0
for node in nodes:
	for nei in adj[node]:
		if nei in nodes:
			tot_sum += adj[node][nei]
print(tot_sum - largest_distance)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


from queue import deque

class City:

	def __init__(self, id):
		(self.id, self.children, self.parent, self.dep, self.maxDep, self.letter, self.totalPath, self.maxPath) = (id, [], None, 0, 0, 0, 0, 0)
(N, K) = map(int, input().strip().split(' '))
(V, f) = ([City(i) for i in range(N + 1)], 0)
for le in map(int, input().strip().split(' ')):
	if f == 0:
		f = le
	V[le].letter = 1
Q = deque([V[f]])
for _ in range(N - 1):
	(u, v, d) = map(int, input().strip().split(' '))
	(V[u].children.append((V[v], d)), V[v].children.append((V[u], d)))
while Q:
	q = Q.pop()
	for i in range(len(q.children)):
		if q.children[i][0] == q.parent:
			q.children[i] = q.children[-1]
			q.children.pop()
			break
	for iq in q.children:
		iq[0].parent = q
		iq[0].dep = q.dep + iq[1]
		Q.append(iq[0])
DS = sorted(V, key=lambda x: -x.dep)
for di in DS:
	dclen = len(di.children)
	if dclen:
		toMaxDepArr = [0] * (dclen + 1)
		for i in range(dclen):
			(ch, w) = di.children[i]
			toMaxDepArr[i] = ch.maxDep + (w if ch.maxDep or ch.letter else 0)
			di.totalPath += ch.totalPath + (w if ch.maxDep or ch.letter else 0)
			if ch.maxPath > di.maxPath:
				di.maxPath = ch.maxPath
		toMaxDepArr.sort()
		di.maxDep = toMaxDepArr[-1]
		di.maxPath = max(di.maxPath, toMaxDepArr[-1] + (toMaxDepArr[-2] if di.letter or toMaxDepArr[-2] else 0))
print(V[f].totalPath * 2 - V[f].maxPath)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


import sys
sys.setrecursionlimit(100000)

class Graph:

	def __init__(self, n, k):
		self.important = {x: False for x in range(1, n + 1)}
		self.nec = {x: False for x in range(1, n + 1)}
		self.m = 0
		self.n = n
		self.k = k
		self.edgesum = 0
		self.edges = {x: [] for x in range(1, n + 1)}

	def dfs(self, node, parent):
		longest = -float('inf')
		second_longest = -float('inf')
		for (neighbour, cost) in self.edges[node]:
			if neighbour == parent:
				continue
			longest_neighbour = self.dfs(neighbour, node)
			second_longest = max(second_longest, longest_neighbour + cost)
			if second_longest > longest:
				(longest, second_longest) = (second_longest, longest)
			self.nec[node] += self.nec[neighbour]
			if self.nec[neighbour] != 0 and self.nec[neighbour] != k:
				self.edgesum += cost
		if second_longest > 0:
			self.m = max(longest + second_longest, self.m)
		if longest > 0 and self.important[node]:
			self.m = max(self.m, longest)
		if self.important[node]:
			longest = max(longest, 0)
		return longest
(n, k) = map(int, input().split())
g = Graph(n, k)
for x in input().split():
	g.important[int(x)] = True
	g.nec[int(x)] = 1
for x in range(n - 1):
	(source, destination, weight) = map(int, input().split())
	g.edges[source].append((destination, weight))
	g.edges[destination].append((source, weight))
g.dfs(1, 1)
print(g.edgesum * 2 - g.m)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


class Node:

	def __init__(self, node_id, parent, parent_weight):
		self.id = node_id
		self.parent = parent
		self.parent_weight = parent_weight
		self.children = []
		self.keep = False
		self.height = 0
		self.weight = 0
		self.diameter = 0

	def make_string(self, level=0):
		return ' ' * level + str(self) + ''.join(('\n' + child.make_string(level + 1) for child in self.children if child.keep))

	def __str__(self):
		return ' '.join((str(x) for x in (self.id + 1, self.height, self.weight, self.diameter, [child.id + 1 for child in self.children if child.keep])))

def max12(g, default=0):
	first = default
	second = default
	for i in g:
		if i > first:
			second = first
			first = i
		elif i > second:
			second = i
	return (first, second)

class Tree:

	def __init__(self, edges, delivery):
		self.root = Node(delivery[0], None, None)
		self.bfs_list = [self.root]
		i = 0
		while i < len(self.bfs_list):
			node = self.bfs_list[i]
			i += 1
			for (child_id, weight) in edges[node.id]:
				if node.parent is None or child_id != node.parent.id:
					node.children.append(Node(child_id, node, weight))
			self.bfs_list += node.children
		self.prune(delivery)
		self.calculate_properties()

	def prune(self, delivery):
		node_list = [None] * len(self.bfs_list)
		for node in self.bfs_list:
			node_list[node.id] = node
		for nodeid in delivery:
			node = node_list[nodeid]
			while node is not None and node.keep is False:
				node.keep = True
				node = node.parent

	def calculate_properties(self):
		self.diameter = 0
		for node in reversed(self.bfs_list):
			if not node.keep:
				continue
			node.weight = sum((child.weight + child.parent_weight for child in node.children if child.keep))
			(first, second) = max12((child.height + child.parent_weight for child in node.children if child.keep))
			node.height = first
			node.diameter = first + second
			self.diameter = max(self.diameter, node.diameter)

	def __str__(self):
		return self.root.make_string()

def main():
	(n, k) = (int(x) for x in input().split())
	delivery = [int(x) - 1 for x in input().split()]
	edges = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v, d) = (int(x) for x in input().split())
		edges[u - 1].append((v - 1, d))
		edges[v - 1].append((u - 1, d))
	tree = Tree(edges, delivery)
	print(2 * tree.root.weight - tree.diameter)
main()


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


class Node:

	def __init__(self):
		self.next = []
		self.dist = []
		self.mail = False
		self.path = []

def get_data():
	(n, _) = map(int, input().split())
	tree = [Node() for _ in range(n)]
	for city in map(int, input().split()):
		tree[city - 1].mail = True
	for _ in range(n - 1):
		(a, b, d) = map(int, input().split())
		a -= 1
		b -= 1
		tree[a].next.append(tree[b])
		tree[b].next.append(tree[a])
		tree[a].dist.append(d)
		tree[b].dist.append(d)
	return tree

def cut_branches(tree):
	leafs = []
	tocut = []
	for node in tree:
		if len(node.next) < 2:
			if node.mail:
				leafs.append(node)
			else:
				tocut.append(node)
	while tocut:
		node = tocut.pop()
		susid = node.next[0]
		i = susid.next.index(node)
		del susid.next[i]
		del susid.dist[i]
		if len(susid.next) < 2:
			if susid.mail:
				leafs.append(susid)
			else:
				tocut.append(susid)
	return leafs

def get_route(leafs):
	result = 0
	longpath = 0
	while len(leafs) > 1:
		node = leafs.pop()
		susid = node.next[0]
		i = susid.next.index(node)
		del susid.next[i]
		del susid.dist[i]
		if len(susid.next) == 1:
			leafs.append(susid)
		result += node.dist[0]
		if node.path:
			if len(node.path) > 1:
				node.path.sort(reverse=True)
				longpath = max(longpath, node.path[0] + node.path[1])
			susid.path.append(node.path[0] + node.dist[0])
		else:
			susid.path.append(node.dist[0])
	node = leafs[0]
	if node.path:
		node.path.sort(reverse=True)
		longpath = max(longpath, sum(node.path[:2]))
	return 2 * result - longpath
result = get_route(cut_branches(get_data()))
print(result)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


import os
import sys

def jeanisRoute(n, k, roads, targets):
	dim = [0] * n
	used = [False] * n
	important = [False] * n
	adj = [[] for i in range(n)]
	for src in targets:
		important[src - 1] = True
	for (src, dest, value) in roads:
		adj[src - 1].append((dest - 1, value))
		adj[dest - 1].append((src - 1, value))
		dim[dest - 1] += 1
		dim[src - 1] += 1
	Q = []
	for src in range(n):
		if dim[src] == 1 and (not important[src]):
			Q.append(src)
			used[src] = True
	while len(Q) != 0:
		src = Q.pop()
		for (dst, value) in adj[src]:
			if used[dst]:
				continue
			dim[dst] -= 1
			if dim[dst] <= 1 and (not important[dst]):
				Q.append(dst)
				used[dst] = True
	weight_sum = 0
	for src in range(n):
		if used[src]:
			continue
		for (dst, value) in adj[src]:
			if used[dst]:
				continue
			weight_sum += value
	Q = []
	for src in range(n):
		if used[src]:
			continue
		important[src] = True
		if dim[src] == 1:
			Q.append(src)
			used[src] = True
	max_path = 0
	max_cont = [0] * n
	while len(Q) != 0:
		src = Q.pop()
		maxes = []
		for (dst, value) in adj[src]:
			if used[dst]:
				if important[dst]:
					maxes.append(max_cont[dst] + value)
			else:
				dim[dst] -= 1
				if dim[dst] <= 1:
					Q.append(dst)
					used[dst] = True
		if len(maxes) == 1:
			max_cont[src] = maxes[0]
		elif len(maxes) >= 2:
			(max_1, max_2) = (max(maxes[0], maxes[1]), min(maxes[0], maxes[1]))
			for x in maxes[2:]:
				if x > max_1:
					(max_1, max_2) = (x, max_1)
				elif x > max_2:
					(max_1, max_2) = (max_1, x)
			max_cont[src] = max_1
			max_path = max(max_path, max_1 + max_2)
		max_path = max(max_path, max_cont[src])
	return weight_sum - max_path
nk = input().split()
n = int(nk[0])
k = int(nk[1])
city = list(map(int, input().rstrip().split()))
roads = []
for _ in range(n - 1):
	roads.append(list(map(int, input().rstrip().split())))
result = jeanisRoute(n, k, roads, city)
print(result)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


import os
import sys
from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


def lstin():
	return list(map(int, input().strip().split()))

def dfs(edges, root):
	stack = [(root, v) for (v, d) in edges[root]]
	flatten = list()
	while stack:
		(u, v) = stack.pop()
		flatten.append((u, v))
		stack.extend(((v, w) for (w, d) in edges[v] if w != u))
	flatten.reverse()
	return flatten

def get_subtree(edges, is_goal, root):
	subt = is_goal[:]
	for (u, v) in dfs(edges, root):
		subt[u] = subt[u] or subt[v]
	return subt

def get_farthest(edges, is_goal, subtree, root):
	visited = [False for _ in edges]
	st = [(0, root)]
	visited[root] = True
	mx = (0, root)
	dist_all = 0
	while st:
		(dist, u) = st.pop()
		for (v, d) in edges[u]:
			if not visited[v] and subtree[v]:
				elm = (dist + d, v)
				dist_all += d
				if is_goal[v]:
					mx = max(mx, elm)
				st.append(elm)
				visited[v] = True
	return (dist_all, mx)
(N, K) = lstin()
goals = lstin()
is_goal = [False] * (N + 1)
for u in goals:
	is_goal[u] = True
edges = [list() for _ in range(N + 1)]
for _ in range(N - 1):
	(u, v, d) = lstin()
	edges[u].append((v, d))
	edges[v].append((u, d))
subtree = get_subtree(edges, is_goal, goals[0])
(_, (_, u)) = get_farthest(edges, is_goal, subtree, goals[0])
(D, (d, _)) = get_farthest(edges, is_goal, subtree, u)
print(2 * D - d)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


def getSubtree(edges, goal, start):
	subt = goal.copy()
	for (u, v) in dfs(edges, start):
		subt[u] = subt[u] or subt[v]
	return subt

def dfs(graph, start):
	s = [(start, v) for (v, d) in graph[start]]
	flatten = list()
	while s:
		(u, v) = s.pop()
		flatten.append((u, v))
		s.extend(((v, w) for (w, d) in graph[v] if w != u))
	flatten.reverse()
	return flatten

def getFarthest(edges, goal, subtree, start):
	visited = [False for _ in edges]
	st = [(0, start)]
	visited[start] = True
	mx = (0, start)
	dist_all = 0
	while st:
		(dist, u) = st.pop()
		for (v, d) in edges[u]:
			if not visited[v] and subtree[v]:
				elm = (dist + d, v)
				dist_all += d
				if goal[v]:
					mx = max(mx, elm)
				st.append(elm)
				visited[v] = True
	return (dist_all, mx)
(N, K) = [int(i) for i in input().split()]
goals = [int(i) for i in input().split()]
is_goal = [False] * (N + 1)
for u in goals:
	is_goal[u] = True
edges = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(u, v, d) = [int(i) for i in input().split()]
	edges[u].append((v, d))
	edges[v].append((u, d))
subtree = getSubtree(edges, is_goal, goals[0])
(maxDis, (_, u)) = getFarthest(edges, is_goal, subtree, goals[0])
(_, (d, _)) = getFarthest(edges, is_goal, subtree, u)
print(2 * maxDis - d)


def farthest_node_from_start(nodes, is_goal, subtree, starting_node):
	visited = [False for _ in nodes]
	st = [(0, starting_node)]
	visited[starting_node] = True
	largest = (0, starting_node)
	all_dist_sum = 0
	while st:
		(dist, u) = st.pop()
		for (v, d) in nodes[u]:
			if not visited[v] and subtree[v]:
				elm = (dist + d, v)
				all_dist_sum += d
				if is_goal[v]:
					largest = max(largest, elm)
				st.append(elm)
				visited[v] = True
	return (all_dist_sum, largest)

def make_subtree(nodes, is_goal, starting_node):
	subtree = is_goal[:]
	for (u, v) in dfs(nodes, starting_node):
		subtree[u] = subtree[u] or subtree[v]
	return subtree

def dfs(nodes, starting_node):
	stack = [(starting_node, v) for (v, d) in nodes[starting_node]]
	edges = list()
	while stack:
		(u, v) = stack.pop()
		edges.append((u, v))
		stack.extend(((v, w) for (w, d) in nodes[v] if w != u))
	edges.reverse()
	return edges
(N, K) = list(map(int, input().strip().split()))
goals = list(map(int, input().strip().split()))
is_goal = [False] * (N + 1)
for item in goals:
	is_goal[item] = True
nodes = [[] for _ in range(N + 1)]
for _ in range(N - 1):
	(u, v, d) = list(map(int, input().strip().split()))
	nodes[u].append((v, d))
	nodes[v].append((u, d))
subtree = make_subtree(nodes, is_goal, goals[0])
(a, (b, c)) = farthest_node_from_start(nodes, is_goal, subtree, goals[0])
(Distance, (d, _)) = farthest_node_from_start(nodes, is_goal, subtree, c)
print(2 * Distance - d)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)


from collections import deque
(N, K) = map(int, input().split())
paths = [[] for i in range(N)]
delivery = set(map(lambda x: int(x) - 1, input().split()))
for i in range(N - 1):
	(frm, to, d) = map(int, input().split())
	paths[frm - 1].append((to - 1, d))
	paths[to - 1].append((frm - 1, d))
parent = [-1] * N
root = next(iter(delivery))
q = deque([root])
while q:
	x = q.popleft()
	for path in paths[x]:
		if path[0] != parent[x]:
			q.append(path[0])
			parent[path[0]] = x
keep = [False] * N
for i in delivery:
	x = i
	while x != -1 and (not keep[x]):
		keep[x] = True
		x = parent[x]
paths = [[path for path in paths[i] if keep[path[0]] and keep[i]] for i in range(N)]

def furthest_vertex(start):
	result = (start, 0)
	visited = [False] * N
	q = deque([result])
	while q:
		x = q.popleft()
		if x[1] > result[1]:
			result = x
		visited[x[0]] = True
		for path in paths[x[0]]:
			if not visited[path[0]]:
				q.append((path[0], x[1] + path[1]))
	return result
start = next((i for (i, x) in enumerate(paths) if len(x)))
longest_path = furthest_vertex(furthest_vertex(start)[0])[1]
print(sum((sum((x[1] for x in l)) for l in paths)) - longest_path)