There is a planet named “Ruizland” having $N$ cities, These cities are connected in the form of a tree by a bidirectional path of specified length(in miles). Cities are numbered from $1$ to $N$. City number $1$ is the capital city.

$M$ pilgrims started their journey from the capital city having initial energy $E_{1}, E_{2}, \ldots, E_{M}$ respectively which reduces on moving from one city to another by a certain amount$(A)$.
$A$ is calculated as follows:-
Consider two cities $U$ and $V$ having an edge length of $K$ miles.
The total number of distinct cities from the capital city to the city $U$ is $D$ (city $U$ and capital city both are inclusive).
If a pilgrim moves from city $U$ to $V$, then $A=K*D$.

Out of $N$ cities, There are some special cities (except the capital city) that are connected to only one city. All pilgrims want to reach any of the special cities. A pilgrim will stop his journey as soon as the energy of the pilgrims becomes $0$ or reaches any of the special cities.

Initially, all cities have $0$ pilgrims except the capital city.

Find the maximum count of special cities that is non-empty (at least one pilgrim is present) after the end of the journey of all the pilgrims given that pilgrims are allowed to take any path during their journey.

------ Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two integers $N$ and $M$ separated by space, where $N$ is the number of cities and $M$ is the number of pilgrims.
The second line contains $M$ integers separated by spaces, denoting the initial energy of the pilgrims.
Next, $N-1$ lines consists of three integers $U$, $V$ and $K$ separated by space where city $U$ and $V$ are connected by a bidirectional path whose length is $K$ miles

------  Output ------
For each test case, Print the maximum count of special cities that is non-empty (at least one pilgrim is present) after the end of the journey of all the pilgrims.

------  Constraints ------
$1 ≤ T ≤ 50$
$2 ≤ N ≤ 10^{5}$
$1 ≤ M ≤ 10^{5}$
$1 ≤ E_{i} ≤ 10^{18}$
$1 ≤ U, V ≤ N$
$1 ≤ K ≤ 10^{6}$
It is guaranteed that the sum of $N$ over all test cases does not exceed $10^{5}$.
It is guaranteed that the sum of $M$ over all test cases does not exceed $10^{5}$.

----- Sample Input 1 ------ 
1
6 4
100 20 10 50
1 2 10
2 3 20
2 4 30
4 5 40
1 6 50
----- Sample Output 1 ------ 
2
----- explanation 1 ------ 
There are $3$ special cities namely $3, 5$ and $6$. The energy expected to reach these special cities are $50, 190$ and $50$ respectively. Special city $5$ cannot be reached by any pilgrim. If Pilgrim $1$ goes to the special city $3$ and pilgrim $4$ goes to the special city $6$, then the maximum number of non-empty special cities is $2$.

Difficulty: HARD
Tags: Graph algorithms

Graph traversal

Sorting

Greedy algorithms

Tree algorithms

Dynamic programming

Data structures
Skill types: Dynamic programming

Sorting

Data structures

Greedy algorithms

Starter code:

Solutions:
import sys
sys.setrecursionlimit(999999999)
from collections import defaultdict

def dfs(node, graph, count, distance):
	global vis
	global arr
	vis[node] = True
	if len(graph[node]) == 1 and node != 0:
		arr.append(distance)
	for i in graph[node]:
		if not vis[i[0]]:
			dfs(i[0], graph, count + 1, distance + (count + 1) * i[1])
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	graph = defaultdict(list)
	for i in range(n - 1):
		(x, b, c) = map(int, input().split())
		x -= 1
		b -= 1
		graph[x].append([b, c])
		graph[b].append([x, c])
	global arr, vis
	arr = []
	vis = [False] * n
	dfs(0, graph, 0, 0)
	a.sort()
	ans = 0
	arr.sort()
	ans = 0
	i = 0
	j = 0
	while i < m and j < len(arr):
		if a[i] >= arr[j]:
			j += 1
			ans += 1
		i += 1
	print(ans)


def finddist():
	allenergy = list()
	from collections import deque
	from queue import Queue
	q = Queue()
	q.put(1)
	distance = defaultdict(int)
	distance[1] = 1
	energy = defaultdict(int)
	while not q.empty():
		cur = q.get()
		vis.add(cur)
		check = 0
		for neigh in graph[cur]:
			if neigh[0] not in vis:
				distance[neigh[0]] = distance[cur] + 1
				energy[neigh[0]] = distance[cur] * neigh[1] + energy[cur]
				q.put(neigh[0])
				check = 1
		if not check:
			special.add(cur)
	for i in special:
		allenergy.append(energy[i])
	return allenergy
for t in range(int(input())):
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	from collections import defaultdict
	graph = defaultdict(list)
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		graph[u].append((v, w))
		graph[v].append((u, w))
	special = set()
	vis = set()
	B = finddist()
	A.sort()
	B.sort()
	l = len(B)
	ind = 0
	cnt = 0
	for i in A:
		if i >= B[ind]:
			ind += 1
			cnt += 1
			if ind >= l:
				break
	print(cnt)


def finddist():
	allenergy = list()
	from collections import deque
	q = deque([1])
	distance = defaultdict(int)
	distance[1] = 1
	energy = defaultdict(int)
	while len(q) != 0:
		cur = q.popleft()
		vis.add(cur)
		check = 0
		for neigh in graph[cur]:
			if neigh[0] not in vis:
				distance[neigh[0]] = distance[cur] + 1
				energy[neigh[0]] = distance[cur] * neigh[1] + energy[cur]
				q.append(neigh[0])
				check = 1
		if not check:
			special.add(cur)
	for i in special:
		allenergy.append(energy[i])
	return allenergy
for t in range(int(input())):
	(n, m) = map(int, input().split())
	A = list(map(int, input().split()))
	from collections import defaultdict
	graph = defaultdict(list)
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		graph[u].append((v, w))
		graph[v].append((u, w))
	special = set()
	vis = set()
	B = finddist()
	A.sort(reverse=True)
	B.sort(reverse=True)
	ind = 0
	ans = 0
	n = len(B)
	j = 0
	for i in range(m):
		while j < n:
			if A[i] < B[j]:
				j = j + 1
			else:
				break
		if j == n:
			break
		if B[j] <= A[i]:
			ans = ans + 1
			j = j + 1
	print(ans)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	d = {}
	dist = {}
	for i in range(1, n + 1):
		d[i] = set()
	for i in range(n - 1):
		(u, v, k) = map(int, input().split())
		d[u].add(v)
		d[v].add(u)
		dist[u, v] = k
		dist[v, u] = k
	visited = set()
	l = []
	l.append((1, 0, 0))
	visited.add(1)
	count = 0
	cost = 0
	e = []
	while l:
		(o, c, count) = l.pop(0)
		num = 0
		for nbour in d[o]:
			if nbour not in visited:
				num = num + 1
				visited.add(nbour)
				cost = c + (count + 1) * dist[o, nbour]
				l.append((nbour, cost, count + 1))
		if num == 0:
			e.append(c)
	arr.sort()
	e.sort()
	i = 0
	ans = 0
	j = 0
	ln1 = len(arr)
	ln2 = len(e)
	while i < ln1 and j < ln2:
		if arr[i] >= e[j]:
			i += 1
			j += 1
			ans += 1
		else:
			i += 1
	print(ans)


import sys, math, itertools, random, bisect
from collections import defaultdict
sys.setrecursionlimit(10 ** 8)
INF = 10 ** 18

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
mod = 10 ** 9 + 7

class Graph:

	def __init__(self, vertices):
		self.graph = [defaultdict() for x in range(vertices)]
		self.V = vertices

	def addEdge(self, u, v, w=0):
		self.graph[u][v] = w
		self.graph[v][u] = w

	def DFSUtil(self, s, visited, store, length, cost):
		visited[s] = True
		if len(self.graph[s]) == 1 and s != 0:
			store.append(cost)
		for v in self.graph[s]:
			if visited[v] == False:
				self.DFSUtil(v, visited, store, length + 1, cost + (length + 1) * self.graph[s][v])

	def DFS(self, s):
		visited = [False] * self.V
		store = []
		self.DFSUtil(s, visited, store, 0, 0)
		return store
for _ in range(int(input())):
	(n, m) = get_ints()
	a = get_array()
	g = Graph(n)
	for i in range(n - 1):
		(u, v, w) = get_ints()
		g.addEdge(u - 1, v - 1, w)
	store = g.DFS(0)
	store.sort()
	a.sort()
	(i, j) = (0, 0)
	ans = 0
	while i < m and j < len(store):
		if a[i] >= store[j]:
			ans += 1
			j += 1
		i += 1
	print(ans)


from collections import deque

def ints():
	return map(int, input().split())

def bfs(v):
	vis = set([v])
	depth = {v: 1}
	dp = {v: 0}
	q = deque([v])
	while q:
		curr = q.popleft()
		for (nbr, w) in graph[curr]:
			if nbr not in vis:
				vis.add(nbr)
				q.append(nbr)
				depth[nbr] = depth[curr] + 1
				dp[nbr] = w * depth[curr] + dp[curr]
	return (depth, dp)
t = int(input())
for _ in range(t):
	(n, m) = ints()
	pil = list(ints())
	graph = {i + 1: [] for i in range(n)}
	for i in range(n - 1):
		(a, b, w) = ints()
		graph[a].append((b, w))
		graph[b].append((a, w))
	(depth, dp) = bfs(1)
	maxx = max(depth.values())
	ans = []
	for e in dp:
		if len(graph[e]) == 1 and e != 1:
			ans.append(dp[e])
	ans = sorted(ans)
	(i, j) = (0, 0)
	pil.sort()
	while i < len(pil) and j < len(ans):
		if pil[i] >= ans[j]:
			i += 1
			j += 1
		else:
			i += 1
	print(j)


import sys
from collections import defaultdict

def pr(n):
	sys.stdout.write(str(n))
	sys.stdout.write('\n')

def inp1():
	return int(sys.stdin.readline())

def inp2():
	return list(map(int, sys.stdin.readline().split()))
import queue

def pt(graph, V, x):
	level = [None] * V
	marked = [False] * V
	ans = [0] * V
	que = queue.Queue()
	que.put(x)
	level[x] = 0
	marked[x] = True
	while not que.empty():
		x = que.get()
		for i in range(len(graph[x])):
			b = graph[x][i][0]
			if not marked[b]:
				que.put(b)
				level[b] = level[x] + 1
				ans[b] = level[b] * graph[x][i][1] + ans[x]
				marked[b] = True
	return ans
for _ in range(int(input())):
	(k, n) = inp2()
	l = inp2()
	G = [[] for i in range(k)]
	for i in range(k - 1):
		(x, y, w) = inp2()
		G[x - 1].append([y - 1, w])
		G[y - 1].append([x - 1, w])
	g = pt(G, k, 0)
	pq = []
	for i in range(k):
		if len(G[i]) == 1 and i != 0:
			pq.append(i)
	lt = []
	for i in pq:
		lt.append(g[i])
	lt.sort()
	f = len(lt)
	l.sort()
	ans = 0
	j = 0
	for i in range(n):
		if j < f and l[i] >= lt[j]:
			j += 1
			ans += 1
	print(ans)


def dfs(node, parent):
	s = set()
	visited[1] = True
	stack = [[node, parent]]
	levelarray[node] = 1
	while stack:
		(node, parent) = stack.pop()
		levelarray[node] += levelarray[parent]
		costarray[node] = costarray[node] + costarray[parent]
		flag = 1
		for (child, cost) in g[node]:
			if visited[child] == False and child != parent:
				costarray[child] += levelarray[node] * cost
				flag = 0
				visited[child] = True
				levelarray[child] += 1
				stack.append([child, node])
		if flag == 1:
			s.add(node)
	return s
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	g = {i: [] for i in range(1, n + 1)}
	s = set()
	visited = [False for i in range(n + 1)]
	levelarray = [0 for i in range(n + 1)]
	costarray = [0 for i in range(n + 1)]
	for i in range(n - 1):
		(u, v, c) = map(int, input().split())
		g[u].append([v, c])
		g[v].append([u, c])
	s = dfs(1, 0)
	p = [costarray[i] for i in s]
	ans = 0
	p.sort()
	a = len(p)
	l.sort()
	i = 0
	ans = 0
	j = 0
	while i < m and j < a:
		if l[i] < p[j]:
			i += 1
		else:
			i += 1
			j += 1
			ans += 1
	print(ans)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

def li():
	return list(map(int, sys.stdin.readline().split()))

def mp():
	return map(int, sys.stdin.readline().split())

def inp():
	return int(sys.stdin.readline())

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	(n, m) = mp()
	l = li()
	d = defaultdict(list)
	v = [0, 0]
	for i in range(n - 1):
		(a, b, c) = mp()
		d[a].append([b, c])
		d[b].append([a, c])
		v.append(0)
	q = deque()
	v[1] = 1
	special = []
	q.append((1, 1, 0))
	backup = defaultdict(int)
	backup[1] = 0
	while q:
		(x, y, s) = q.popleft()
		if x != 1 and len(d[x]) == 1:
			special.append(s)
		for i in d[x]:
			(fu, ck) = i
			if not v[fu]:
				v[fu] = 1
				backup[fu] = s + y * ck
				q.append((fu, y + 1, backup[fu]))
	special.sort()
	a = len(special)
	l.sort()
	i = 0
	ans = 0
	j = 0
	while i < m and j < a:
		if l[i] < special[j]:
			i += 1
		else:
			i += 1
			j += 1
			ans += 1
	pr(ans)
for _ in range(inp()):
	solve()


from sys import setrecursionlimit
setrecursionlimit(10 ** 8)

def dfs(p, prev, val, d):
	for i in child[p]:
		if i[0] != prev:
			dfs(i[0], p, val + i[1] * d, d + 1)
	if len(child[p]) == 1 and prev != 0:
		x.append(val)

def answer():
	(ans, ind) = (0, 0)
	for i in range(len(x)):
		for j in range(ind, len(e)):
			if e[j] >= x[i]:
				ind = j + 1
				ans += 1
				break
	return ans
for T in range(int(input())):
	(n, m) = map(int, input().split())
	e = sorted(list(map(int, input().split())))
	child = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v, k) = map(int, input().split())
		child[u].append([v, k])
		child[v].append([u, k])
	x = []
	dfs(1, 0, 0, 1)
	x.sort()
	print(answer())


import sys
sys.setrecursionlimit(10 ** 8)

def dfs(node, e, parent, d):
	isLeaf = True
	for (v, k) in Edges[node]:
		if v != parent:
			dfs(v, e + k * d, node, d + 1)
			isLeaf = False
	if isLeaf:
		SCE.append(e)
t = int(input())
for tc in range(t):
	(n, m) = map(int, input().split())
	PE = [0] + list(map(int, input().split()))
	Edges = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v, k) = map(int, input().split())
		Edges[u].append([v, k])
		Edges[v].append([u, k])
	SCE = []
	dfs(1, 0, 0, 1)
	count = 0
	PE = sorted(PE)
	SCE = sorted(SCE)
	j = m
	for i in range(len(SCE) - 1, -1, -1):
		if j > 0 and SCE[i] <= PE[j]:
			count += 1
			j -= 1
	print(count)


import sys
from collections import deque
sys.setrecursionlimit(10 ** 6)
from queue import PriorityQueue
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7

def dfs(u, par, d):
	if len(adj[u]) == 1 and u != 0:
		mn.append(a[u])
		return
	for [i, j] in adj[u]:
		if i == par:
			continue
		a[i] = a[u] + d * j
		dfs(i, u, d + 1)
for _ in range(ii()):
	(n, m) = il()
	e = il()
	a = [0 for i in range(n)]
	adj = [[] for i in range(n)]
	mn = []
	for i in range(n - 1):
		(x, y, k) = il()
		x -= 1
		y -= 1
		adj[x].append([y, k])
		adj[y].append([x, k])
	dfs(0, -1, 1)
	e.sort(reverse=True)
	mn.sort(reverse=True)
	ans = 0
	i = 0
	j = 0
	l1 = len(mn)
	while i < l1 and j < m:
		if mn[i] > e[j]:
			i += 1
		else:
			i += 1
			ans += 1
			j += 1
	print(ans)


import math, bisect as bi, sys, resource
from collections import defaultdict as dd, deque as dq

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

def Sn():
	return stdin.readline().strip()
resource.setrlimit(resource.RLIMIT_STACK, (2 ** 29, -1))
sys.setrecursionlimit(10 ** 6)

def yes():
	print('YES')

def no():
	print('NO')

def find_ge(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	raise len(a) - 1

def dfs(node, cost, parent):
	dp[node] = dp[parent] + cost * high[node]
	if len(gp[node]) == 1:
		if parent == gp[node][0][0]:
			leaf.append(dp[node])
	for (x, val) in gp[node]:
		if high[x] == -1:
			high[x] = high[node] + 1
			dfs(x, val, node)

def main():
	try:
		global n, m, dp, gp, leaf, high
		(n, m) = In()
		pril = list(In())
		pril.sort()
		dp = [0] * (n + 1)
		high = [-1] * (n + 1)
		high[1] = 0
		leaf = []
		gp = dd(list)
		for i in range(n - 1):
			(a, b, c) = In()
			gp[a].append((b, c))
			gp[b].append((a, c))
		dfs(1, 0, 1)
		leaf.sort()
		ans = 0
		j = 0
		for i in range(len(pril)):
			if j < len(leaf) and leaf[j] <= pril[i]:
				ans += 1
				j += 1
		print(ans)
	except:
		pass
M = 998244353
P = 1000000007
TEST = I()
for _ in range(TEST):
	main()


import sys
sys.setrecursionlimit(10 ** 9)

def traverse(n, m, adjList, sp, src, visited, u, prev):
	if len(adjList[src]) == 1 and visited[adjList[src][0][0]]:
		sp.append(prev)
	else:
		for a in adjList[src]:
			if not visited[a[0]]:
				visited[a[0]] = True
				traverse(n, m, adjList, sp, a[0], visited, u + 1, prev + a[1] * u)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	e = sorted(list(map(int, input().split())))
	adjList = [[] for _ in range(n)]
	for _ in range(n - 1):
		(a, b, k) = map(int, input().split())
		a -= 1
		b -= 1
		adjList[a].append([b, k])
		adjList[b].append([a, k])
	sp = []
	visited = [False] * n
	visited[0] = True
	traverse(n, m, adjList, sp, 0, visited, 1, 0)
	sp.sort()
	i = 0
	j = 0
	while i < len(e) and j < len(sp):
		if sp[j] <= e[i]:
			i += 1
			j += 1
		else:
			i += 1
	print(j)


import sys, os
from io import BytesIO, IOBase
mod = 10 ** 9 + 7
Mod = 998244353
INF = float('inf')
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda : list(map(int, sys.stdin.readline().rstrip('\r\n').split()))
sys.setrecursionlimit(100000 + 10)
tc = 1
tc = int(input())
for test in range(1, tc + 1):
	(n, m) = inp()
	a = inp()
	g = [[] for i in range(n)]
	for i in range(n - 1):
		(p, q, d) = inp()
		g[p - 1].append((q - 1, d))
		g[q - 1].append((p - 1, d))
	ans = [INF] * n

	def dfs(node, dis, par, res):
		if len(g[node]) == 1 and g[node][0][0] == par:
			ans[node - 1] = res
		else:
			for to in g[node]:
				if to[0] == par:
					continue
				dfs(to[0], dis + 1, node, res + dis * to[1])
	a.sort()
	res = 0
	dfs(0, 1, -1, 0)
	ans.sort()
	i = 0
	j = 0
	while i < m:
		if a[i] < ans[j]:
			i += 1
		else:
			res += 1
			i += 1
			j += 1
	print(res)


import sys
from sys import stdin, stdout
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from collections import deque
test = int(input())
for _ in range(test):
	(n, m) = map(int, input().split())
	energy = list(map(int, input().split()))
	dic = {}
	graph = [[] for i in range(n)]
	for i in range(n - 1):
		(a, b, x) = map(int, input().split())
		(a, b) = (a - 1, b - 1)
		if a > b:
			(a, b) = (b, a)
		dic[a, b] = x
		graph[a].append(b)
		graph[b].append(a)
	dp = [0] * n
	level = dd(list)
	dist = [0] * n
	visited = [False] * n
	parent = [-1] * n
	leaf = []
	src = 0
	q = deque([])
	q.append(src)
	visited[src] = True
	dist[src] = 1
	while q:
		node = q.popleft()
		l = True
		for neighbour in graph[node]:
			if not visited[neighbour]:
				l = False
				q.append(neighbour)
				visited[neighbour] = True
				dist[neighbour] = dist[node] + 1
				parent[neighbour] = node
				level[dist[neighbour]].append(neighbour)
				(a, b) = (node, neighbour)
				if a > b:
					(a, b) = (b, a)
				val = dic[a, b]
				dp[neighbour] = dp[node] + dist[node] * val
		if l:
			leaf.append(node)
	cur = []
	for i in leaf:
		cur.append(dp[i])
	cur.sort()
	energy.sort()
	cur = cur[::-1]
	energy = energy[::-1]
	pt1 = 0
	pt2 = 0
	ans = 0
	while pt1 < len(energy) and pt2 < len(cur):
		if energy[pt1] >= cur[pt2]:
			ans += 1
			pt1 += 1
			pt2 += 1
		else:
			pt2 += 1
	print(ans)


import sys
sys.setrecursionlimit(1000001)

def dfs(start, par, ln, val):
	foo = 0
	ln += 1
	for child in adj[start]:
		if child[0] != par:
			foo = 1
			amt = child[1]
			dfs(child[0], start, ln, val + ln * amt)
	if foo == 0:
		arr.append(val)
for y in range(int(input())):
	(n, m) = map(int, input().split())
	lst = list(map(int, input().split()))
	adj = []
	for i in range(n):
		adj.append([])
	for i in range(n - 1):
		(a, b, c) = map(int, input().split())
		adj[a - 1].append([b - 1, c])
		adj[b - 1].append([a - 1, c])
	arr = []
	dfs(0, -1, 0, 0)
	arr.sort()
	lst.sort()
	i = 0
	cnt = 0
	j = 0
	ln1 = len(lst)
	ln2 = len(arr)
	while i < ln1 and j < ln2:
		if lst[i] >= arr[j]:
			i += 1
			j += 1
			cnt += 1
		else:
			i += 1
	print(cnt)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from collections import OrderedDict as od
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
from itertools import accumulate as ac
mod = int(1000000000.0) + 7

def addEdge(a, b):
	graph[a].append(b)
	graph[b].append(a)

def Bfs(src):
	q = deque([])
	q.append(src)
	visited[src] = True
	dist[src] = 1
	dp
	while q:
		node = q.popleft()
		l = True
		for neighbour in graph[node]:
			if not visited[neighbour]:
				l = False
				q.append(neighbour)
				visited[neighbour] = True
				dist[neighbour] = dist[node] + 1
				parent[neighbour] = node
				level[dist[neighbour]].append(neighbour)
				(a, b) = (node, neighbour)
				if a > b:
					(a, b) = (b, a)
				val = dic[a, b]
				dp[neighbour] = dp[node] + dist[node] * val
		if l:
			leaf.append(node)
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')
t = ip()
for _ in range(t):
	(n, m) = inp()
	energy = list(inp())
	dic = {}
	graph = [[] for i in range(n)]
	for i in range(n - 1):
		(a, b, x) = inp()
		(a, b) = (a - 1, b - 1)
		if a > b:
			(a, b) = (b, a)
		dic[a, b] = x
		addEdge(a, b)
	dp = [0] * n
	level = dd(list)
	dist = [0] * n
	visited = [False] * n
	parent = [-1] * n
	leaf = []
	Bfs(0)
	cur = []
	for i in leaf:
		cur.append(dp[i])
	cur.sort(reverse=True)
	energy.sort(reverse=True)
	pt1 = 0
	pt2 = 0
	ans = 0
	while pt1 < len(energy) and pt2 < len(cur):
		if energy[pt1] >= cur[pt2]:
			ans += 1
			pt1 += 1
			pt2 += 1
		else:
			pt2 += 1
	print(ans)