Easy and hard versions are actually different problems, so we advise you to read both statements carefully.

You are given a weighted rooted tree, vertex 1 is the root of this tree.

A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. A parent of a vertex v is the last different from v vertex on the path from the root to the vertex v. Children of vertex v are all vertices for which v is the parent. A vertex is a leaf if it has no children. The weighted tree is such a tree that each edge of this tree has some weight.

The weight of the path is the sum of edges weights on this path. The weight of the path from the vertex to itself is 0.

You can make a sequence of zero or more moves. On each move, you select an edge and divide its weight by 2 rounding down. More formally, during one move, you choose some edge i and divide its weight by 2 rounding down (w_i := \left⌊(w_i)/(2)\right⌋).

Your task is to find the minimum number of moves required to make the sum of weights of paths from the root to each leaf at most S. In other words, if w(i, j) is the weight of the path from the vertex i to the vertex j, then you have to make ∑_{v ∈ leaves} w(root, v) ≤ S, where leaves is the list of all leaves.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 2 ⋅ 10^4) — the number of test cases. Then t test cases follow.

The first line of the test case contains two integers n and S (2 ≤ n ≤ 10^5; 1 ≤ S ≤ 10^{16}) — the number of vertices in the tree and the maximum possible sum of weights you have to obtain. The next n-1 lines describe edges of the tree. The edge i is described as three integers v_i, u_i and w_i (1 ≤ v_i, u_i ≤ n; 1 ≤ w_i ≤ 10^6), where v_i and u_i are vertices the edge i connects and w_i is the weight of this edge.

It is guaranteed that the sum of n does not exceed 10^5 (∑ n ≤ 10^5).

Output

For each test case, print the answer: the minimum number of moves required to make the sum of weights of paths from the root to each leaf at most S.

Example

Input


3
3 20
2 1 8
3 1 7
5 50
1 3 100
1 5 10
2 3 123
5 4 55
2 100
1 2 409


Output


0
8
3

Source: codeforces | Difficulty: HARD
Tags: Tree algorithms

Data structures

Graph traversal

Greedy algorithms


Solutions:
import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict
from bisect import bisect_left as bl, bisect_right as br
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify

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] = 0
	while q:
		node = q.popleft()
		flag = True
		for neighbour in graph[node]:
			if not visited[neighbour]:
				flag = False
				q.append(neighbour)
				visited[neighbour] = True
				dist[neighbour] = dist[node] + 1
				parent[neighbour] = node
				level[dist[neighbour]].append(neighbour)
		if flag:
			leaf.append(node)
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
t = ip()
for _ in range(t):
	(n, s) = inp()
	graph = [[] for i in range(n)]
	visited = [False] * n
	leaf = []
	dist = [0] * n
	parent = [-1] * n
	level = defaultdict(list)
	val = {}
	for i in range(n - 1):
		(a, b, v) = inp()
		(a, b) = (a - 1, b - 1)
		if a > b:
			(a, b) = (b, a)
		val[a, b] = v
		addEdge(a, b)
	Bfs(0)
	ch = sorted(list(level), reverse=True)
	ct = [0] * n
	for i in leaf:
		ct[i] = 1
	sums = []
	checksum = 0
	for i in ch:
		for j in level[i]:
			par = parent[j]
			ct[par] += ct[j]
			(a, b) = (j, par)
			if a > b:
				(a, b) = (b, a)
			weight = val[a, b]
			checksum += weight * ct[j]
			while weight:
				impact = (weight - weight // 2) * ct[j]
				weight = weight // 2
				sums.append(impact)
	sums.sort(reverse=True)
	idx = 0
	ans = 0
	while checksum > s:
		checksum -= sums[idx]
		idx += 1
		ans += 1
	print(ans)


from collections import defaultdict, deque
from bisect import bisect_left as lower
import heapq
import sys, threading
input = sys.stdin.readline

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

def dfs(tree, i, sum, p):
	if len(tree[i]) == 1 and i != 0:
		return 1
	c = 0
	for (j, k) in tree[i]:
		if j != p:
			z = dfs(tree, j, sum + k, i)
			c += z
			arr.append((k, z))
	return c

def solve():
	t = int(input())
	for _ in range(t):
		(n, w) = put()
		tree = [[] for i in range(n)]
		for i in range(n - 1):
			(x, y, z) = put()
			(x, y) = (x - 1, y - 1)
			tree[x].append((y, z))
			tree[y].append((x, z))
		c = dfs(tree, 0, 0, -1)
		s = 0
		for i in range(len(arr)):
			s += arr[i][0] * arr[i][1]
		d = []
		while arr:
			(i, j) = arr.pop()
			while i > 0:
				d.append((i - i // 2) * j)
				i //= 2
		d.sort()
		i = len(d) - 1
		cnt = 0
		while s > w:
			s -= d[i]
			i -= 1
			cnt += 1
		print(cnt)
arr = []
max_recur_size = 10 ** 5 * 2 + 1000
max_stack_size = max_recur_size * 500
sys.setrecursionlimit(max_recur_size)
threading.stack_size(max_stack_size)
thread = threading.Thread(target=solve)
thread.start()


import math, sys, bisect, heapq
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda : map(int, input().split())
alele = lambda : list(map(int, input().split()))

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])
G = defaultdict(list)
first = 0
parents = []
order = []

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

def DFSutil(node, parents, order):
	my_que = deque()
	my_que.append(node)
	while len(my_que) > 0:
		index = my_que.pop()
		for edge in G.get(index, []):
			if parents[edge] == -2:
				my_que.append(edge)
				parents[edge] = index
				order.append(edge)

def findsubtree(first, N):
	parents = [-2 for i in range(N)]
	parents[0] = -1
	order = [0]
	size = [0] * N
	for i in range(N):
		if len(G[i]) == 1:
			size[i] = 1
	DFSutil(first, parents, order)
	for z in range(N - 1, 0, -1):
		bb = order[z]
		size[parents[bb]] += size[bb]
	return (size, parents)

def fun(a, b):
	return a * b - a // 2 * b
for _ in range(int(input())):
	G = defaultdict(list)
	parents = []
	order = []
	(N, S) = ilele()
	E = []
	mark = {}
	for i in range(N - 1):
		(u, v, w) = ilele()
		u -= 1
		v -= 1
		addEdge(u, v)
		mark[u, v] = w
		mark[v, u] = w
	(X, par) = findsubtree(first, N)
	H = []
	tot = 0
	for i in range(1, N):
		e = par[i]
		c = mark[e, i]
		d = X[i]
		tot += d * c
		while fun(c, d):
			H.append(fun(c, d))
			c = c // 2
	if tot <= S:
		print(0)
	else:
		H.sort()
		count = 0
		while tot > S and len(H) > 0:
			tot -= H.pop()
			count += 1
		print(count)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	from collections import deque
	from itertools import accumulate
	input = sys.stdin.buffer.readline
	for _ in range(int(input())):
		(N, S) = map(int, input().split())
		adj = [[] for _ in range(N + 1)]
		for _ in range(N - 1):
			(a, b, c, d) = map(int, input().split())
			adj[a].append((b, c, d))
			adj[b].append((a, c, d))
		que = deque()
		que.append(1)
		seen = [-1] * (N + 1)
		seen[1] = 0
		par = [0] * (N + 1)
		child = [[] for _ in range(N + 1)]
		seq = []
		C = [0] * (N + 1)
		D = [0] * (N + 1)
		while que:
			v = que.popleft()
			seq.append(v)
			for (u, c, d) in adj[v]:
				if seen[u] == -1:
					seen[u] = seen[v] + 1
					par[u] = v
					child[v].append(u)
					que.append(u)
					C[u] = c
					D[u] = d
		seq.reverse()
		dp = [0] * (N + 1)
		T = 0
		D1_ = [[] for _ in range(40)]
		D2_ = [[] for _ in range(40)]
		for v in seq:
			if not child[v]:
				dp[v] = 1
			else:
				for u in child[v]:
					dp[v] += dp[u]
			c = C[v]
			d = D[v]
			num = dp[v]
			T += c * num
			while c:
				val = (c + 1) // 2 * num
				k = len(bin(val)) - 2
				if d == 1:
					D1_[k].append(val)
				else:
					D2_[k].append(val)
				c //= 2
		for i in range(40):
			D1_[i].sort(reverse=True)
			D2_[i].sort(reverse=True)
		D1 = []
		D2 = []
		for i in range(39, -1, -1):
			D1.extend(D1_[i])
			D2.extend(D2_[i])
		cs_D1 = [0] + list(accumulate(D1))
		cs_D2 = [0] + list(accumulate(D2))
		i1 = len(D1) + 1
		i2 = 0
		ans = len(D1) + len(D2) * 2
		flg = 0
		for _ in range(len(D1) + 1):
			i1 -= 1
			t = T - cs_D1[i1] - cs_D2[i2]
			while t > S:
				i2 += 1
				if i2 == len(cs_D2):
					flg = 1
					break
				t = T - cs_D1[i1] - cs_D2[i2]
			if flg:
				break
			ans = min(ans, i1 + i2 * 2)
		print(ans)
main()


from collections import deque
from heapq import heappop, heappush
import sys
input = sys.stdin.readline

def solve():
	(n, s) = map(int, input().split())
	e = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		u -= 1
		v -= 1
		e[u].append((v, w))
		e[v].append((u, w))
	par = [-1] * n
	dep = [n] * n
	dep[0] = 0
	topo = []
	q = deque([0])
	count = [0] * n
	while q:
		now = q.pop()
		topo.append(now)
		lea = 1
		for (nex, _) in e[now]:
			if dep[nex] < dep[now]:
				continue
			lea = 0
			par[nex] = now
			dep[nex] = dep[now] + 1
			q.append(nex)
		if lea:
			count[now] = 1
	cum = 0
	h = []
	for now in topo[::-1]:
		c = count[now]
		for (nex, w) in e[now]:
			if dep[nex] > dep[now]:
				continue
			heappush(h, ((-w + w // 2) * c, w))
			cum += c * w
			count[nex] += c
	ans = 0
	while cum > s:
		(a, w) = heappop(h)
		a *= -1
		nw = w // 2
		c = a // (w - nw)
		ans += 1
		cum -= a
		heappush(h, ((-nw + nw // 2) * c, nw))
	return ans
t = int(input())
for _ in range(t):
	print(solve())


import math, sys, bisect, heapq, os
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
pr = lambda x: x
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
aj = lambda : list(map(int, input().split()))

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])

def solve():
	G = defaultdict(list)
	first = 0
	parents = []
	order = []

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

	def DFSutil(node, parents, order):
		my_que = deque()
		my_que.append(node)
		while len(my_que) > 0:
			index = my_que.pop()
			for edge in G.get(index, []):
				if parents[edge] == -2:
					my_que.append(edge)
					parents[edge] = index
					order.append(edge)

	def findsubtree(first, N):
		parents = [-2 for i in range(N)]
		parents[0] = -1
		order = [0]
		size = [0] * N
		for i in range(N):
			if len(G[i]) == 1:
				size[i] = 1
		DFSutil(first, parents, order)
		for z in range(N - 1, 0, -1):
			bb = order[z]
			size[parents[bb]] += size[bb]
		return (size, parents)

	def fun(a, b):
		return a * b - a // 2 * b
	for _ in range(int(input())):
		G = defaultdict(list)
		parents = []
		order = []
		(N, S) = aj()
		E = []
		mark = {}
		for i in range(N - 1):
			(u, v, w, cst) = aj()
			u -= 1
			v -= 1
			addEdge(u, v)
			mark[u, v] = (w, cst)
			mark[v, u] = (w, cst)
		(X, par) = findsubtree(first, N)
		H1 = []
		H2 = []
		tot = 0
		for i in range(1, N):
			e = par[i]
			(c, cst) = mark[e, i]
			d = X[i]
			tot += d * c
			if cst == 2:
				while fun(c, d):
					H2.append(fun(c, d))
					c = c // 2
			else:
				while fun(c, d):
					H1.append(fun(c, d))
					c = c // 2
		if tot <= S:
			print(0)
		else:
			que1 = sorted(H1, reverse=True)
			que2 = sorted(H2, reverse=True)
			(n, m) = (len(que1), len(que2))
			que2 = list(accumulate(que2))
			que2 = [0] + que2
			que1 = [0] + que1
			ans = float('inf')
			id = m + 1
			cum = 0
			s = tot
			j = m
			for i in range(n + 1):
				test = i
				cum += que1[i]
				while j >= 0 and s - S - cum <= que2[j]:
					j -= 1
				id = j + 1
				if id != m + 1:
					test += 2 * id
					ans = min(ans, test)
			print(ans)
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	from aj import *
except:
	pass
solve()


import io, os
import sys
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import defaultdict
t = int(input())
for ii in range(t):
	graph = defaultdict(list)
	weight = dict()
	(n, s) = map(int, input().split())
	for i in range(n - 1):
		(v, u, w, c) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
		weight[min(u, v), max(u, v)] = (w, c)
	(one, two, leafcount, total) = ([], [], [0] * (n + 1), 0)
	OBSERVE = 0
	CHECK = 1
	stack = [(OBSERVE, 1, 0)]
	while len(stack):
		(state, vertex, parent) = stack.pop()
		if state == OBSERVE:
			stack.append((CHECK, vertex, parent))
			for child in graph[vertex]:
				if child != parent:
					stack.append((OBSERVE, child, vertex))
		else:
			if len(graph[vertex]) == 1:
				leafcount[vertex] = 1
			for child in graph[vertex]:
				if child != parent:
					leafcount[vertex] += leafcount[child]
					total += weight[min(vertex, child), max(vertex, child)][0] * leafcount[child]
					(weigh, cost) = weight[min(vertex, child), max(vertex, child)]
					if cost == 1:
						while weigh:
							one.append(leafcount[child] * (weigh - weigh // 2))
							weigh //= 2
					else:
						while weigh:
							two.append(leafcount[child] * (weigh - weigh // 2))
							weigh //= 2
	one.sort(reverse=True)
	two.sort(reverse=True)
	res = total
	if s >= total:
		print(0)
		continue
	count = 0
	for i in range(len(one)):
		if total - one[i] <= s:
			total -= one[i]
			count += 1
			break
		total -= one[i]
		count += 1
	pq = count
	ind = 0
	if total > s:
		for i in range(len(two)):
			if total - two[i] <= s:
				total -= two[i]
				count += 2
				ind = i + 1
				break
			total -= two[i]
			count += 2
	for i in range(pq - 1, -1, -1):
		if total + one[i] <= s:
			count -= 1
			total += one[i]
		else:
			break
	ind2 = i
	ans = []
	ans.append(count)
	if ind2 >= 2:
		copy = res - total
		if ind < len(two):
			copy += two[ind]
			count += 2
		while True:
			if ind2 >= len(one) or ind2 < 0:
				break
			if res - (copy - one[ind2]) <= s:
				copy -= one[ind2]
				ind2 -= 1
				count -= 1
				ans.append(count)
			else:
				ind += 1
				if ind < len(two):
					count += 2
					copy += two[ind]
			if ind >= len(two):
				break
	sys.stdout.write(str(min(ans)) + '\n')


import sys, threading, math, heapq, collections, itertools, bisect
sys.setrecursionlimit(101000)

def solve(n, s, graph, edges):
	cnt = [0] * len(edges)
	depth = [-1] * n
	stack = [(0, -1, -1)]
	while stack:
		(nodeid, parent, edge) = stack[-1]
		child_exist = False
		for (cid, eid) in graph[nodeid]:
			if cid != parent and depth[cid] == -1:
				child_exist = True
				stack.append((cid, nodeid, eid))
		if not child_exist:
			stack.pop()
			depth[nodeid] = 0
			for (cid, _) in graph[nodeid]:
				if cid != parent:
					depth[nodeid] += depth[cid]
			if depth[nodeid] == 0:
				depth[nodeid] = 1
			if edge != -1:
				cnt[edge] += depth[nodeid]
	h = []
	total = 0
	for (eid, f) in enumerate(cnt):
		curr = f * edges[eid]
		total += curr
		diff = curr - f * (edges[eid] // 2)
		h.append((-diff, eid))
	heapq.heapify(h)
	sol = 0
	while total > s:
		(d, eid) = heapq.heappop(h)
		d = -d
		edges[eid] //= 2
		ntotal = cnt[eid] * edges[eid]
		total -= d
		diff = ntotal - cnt[eid] * (edges[eid] // 2)
		heapq.heappush(h, (-diff, eid))
		sol += 1
	return sol
t = int(input())
for _ in range(t):
	(n, s) = map(int, input().split())
	graph = [[] for _ in range(n)]
	edges = []
	for _ in range(n - 1):
		(f, t, w) = map(int, input().split())
		(f, t) = (f - 1, t - 1)
		edges.append(w)
		graph[f].append((t, len(edges) - 1))
		graph[t].append((f, len(edges) - 1))
	print(solve(n, s, graph, edges))


from heapq import heappush, heappop

def solve(n, S, tree):
	cur = 1
	edges = []
	dfs(1, -1, tree, edges, n)
	pq = []
	sum = 0
	for (weight, cnt) in edges:
		sum += weight * cnt
		while weight > 0:
			diff = (weight - weight // 2) * cnt
			heappush(pq, -diff)
			weight = weight // 2
	res = 0
	while len(pq) > 0 and sum > S:
		cur = heappop(pq)
		sum += cur
		res += 1
	print(res)
	return

def dfs(root, parent, tree, edges, n):
	stack = []
	arr = [0 for _ in range(0, n + 1)]
	stack.append((1, -1))
	while len(stack) > 0:
		(cur, prev) = stack[-1]
		if len(tree[cur]) == 1 and cur != 1:
			stack.pop()
			arr[cur] = 1
			continue
		cnt = 0
		for (child, weight) in tree[cur]:
			if child == prev:
				continue
			cnt += arr[child]
			if arr[child] == 0:
				stack.append((child, cur))
			else:
				edges.append((weight, arr[child]))
		if cnt != 0:
			stack.pop()
			arr[cur] = cnt
	return
t = int(input())
for i in range(0, t):
	(n, S) = map(int, input().split())
	tree = [[] for _ in range(0, n + 1)]
	for j in range(0, n - 1):
		(a, b, c) = map(int, input().split())
		tree[a].append((b, c))
		tree[b].append((a, c))
	solve(n, S, tree)


mod = 1000000007
eps = 10 ** (-9)

def main():
	import sys
	from collections import deque
	from heapq import heappop, heappush
	input = sys.stdin.buffer.readline
	for _ in range(int(input())):
		(N, S) = map(int, input().split())
		adj = [[] for _ in range(N + 1)]
		for _ in range(N - 1):
			(a, b, c) = map(int, input().split())
			adj[a].append((b, c))
			adj[b].append((a, c))
		que = deque()
		que.append(1)
		seen = [-1] * (N + 1)
		seen[1] = 0
		par = [0] * (N + 1)
		child = [[] for _ in range(N + 1)]
		seq = []
		C = [0] * (N + 1)
		while que:
			v = que.popleft()
			seq.append(v)
			for (u, c) in adj[v]:
				if seen[u] == -1:
					seen[u] = seen[v] + 1
					par[u] = v
					child[v].append(u)
					que.append(u)
					C[u] = c
		seq.reverse()
		dp = [0] * (N + 1)
		pq = []
		T = 0
		for v in seq:
			if not child[v]:
				dp[v] = 1
			else:
				for u in child[v]:
					dp[v] += dp[u]
			heappush(pq, -(((C[v] + 1) // 2 * dp[v] << 21) + v))
			T += C[v] * dp[v]
		ans = 0
		while T > S:
			x = heappop(pq)
			v = -x & (1 << 21) - 1
			T -= (C[v] + 1) // 2 * dp[v]
			C[v] //= 2
			if C[v]:
				heappush(pq, -(((C[v] + 1) // 2 * dp[v] << 21) + v))
			ans += 1
		print(ans)
main()


import io
import os
from heapq import heapify, heappush, heappop
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
inf = float('inf')

def solve(N, S, edges):
	graph = [[] for i in range(N)]
	for (u, v, w) in edges:
		u -= 1
		v -= 1
		graph[u].append(v)
		graph[v].append(u)
	numLeaves = [0 for i in range(N)]
	parent = [0 for i in range(N)]

	@bootstrap
	def dfs(node, p):
		parent[node] = p
		leaves = 0
		for child in graph[node]:
			if child != p:
				yield dfs(child, node)
				leaves += numLeaves[child]
		if not leaves:
			numLeaves[node] = 1
		else:
			numLeaves[node] = leaves
		yield
	dfs(0, -1)
	W = [0 for i in range(N)]
	for (u, v, w) in edges:
		u -= 1
		v -= 1
		if parent[u] == v:
			W[u] = w
		else:
			assert parent[v] == u
			W[v] = w
	currCost = 0
	heap = []
	for i in range(N):
		w = W[i]
		l = numLeaves[i]
		currCost += w * l
		newW = w // 2
		decrease = float((newW - w) * l)
		heap.append((decrease, float(i)))
	heapify(heap)
	ans = 0
	while currCost > S:
		(delta, node) = heappop(heap)
		currCost += delta
		ans += 1
		node = int(node)
		W[node] //= 2
		w = W[node]
		if w != 0:
			l = numLeaves[node]
			newW = w // 2
			decrease = float((newW - w) * l)
			heappush(heap, (decrease, float(node)))
	return ans
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
TC = int(input())
for tc in range(1, TC + 1):
	(N, S) = [int(x) for x in input().split()]
	edges = [[int(x) for x in input().split()] for i in range(N - 1)]
	ans = solve(N, S, edges)
	print(ans)


import io
import os
import heapq
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_str():
	return input().decode().strip()

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

def oint():
	return int(input())

def make_item(i, ww=-1):
	if ww == -1:
		ww = w[i]
	return (mul[i] * (ww // 2) - mul[i] * ww, i)

def push_item(i):
	if w[i]:
		if c[i] == 1:
			pq = pq1
		else:
			pq = pq2
		heapq.heappush(pq, make_item(i))

def move(pq):
	global cost
	global sum_
	(diff, i) = heapq.heappop(pq)
	sum_ += diff
	cost += c[i]
	w[i] //= 2
	push_item(i)

def dfs():
	stack = [1]
	visit = [0] * (n + 1)
	while stack:
		i = stack[-1]
		if visit[i] == 0:
			visit[i] = 1
			for (ni, nw, nc) in adj[i]:
				if visit[ni] == 0:
					w[ni] = nw
					c[ni] = nc
					stack.append(ni)
		else:
			visit[i] = 2
			stack.pop()
			if len(adj[i]) == 1:
				mul[i] += 1
			for (ni, _, _) in adj[i]:
				mul[i] += mul[ni]
			push_item(i)
t = oint()
for _ in range(t):
	(n, s) = rint()
	adj = [[] for i in range(n + 1)]
	mul = [0] * (n + 1)
	w = [0] * (n + 1)
	c = [1] * (n + 1)
	pq1 = []
	pq2 = []
	for i in range(n - 1):
		(vv, uu, ww, cc) = rint()
		adj[vv].append((uu, ww, cc))
		adj[uu].append((vv, ww, cc))
	dfs()
	sum_ = 0
	for (_, i) in pq1 + pq2:
		sum_ += mul[i] * w[i]
	cost = 0
	while sum_ > s:
		if not pq1:
			move(pq2)
			continue
		if not pq2:
			move(pq1)
			continue
		if pq1[0][0] + sum_ <= s:
			cost += 1
			break
		if pq2[0][0] + sum_ <= s:
			cost += 2
			break
		(diff1, i1) = heapq.heappop(pq1)
		(diff1r, _) = make_item(i1, w[i1] // 2)
		if pq1:
			diff1n = min(diff1r, pq1[0][0])
		else:
			diff1n = diff1r
		push_item(i1)
		(diff2, i2) = (pq2[0][0], pq2[0][1])
		if diff2 < diff1 + diff1n:
			move(pq2)
		else:
			move(pq1)
	print(cost)


from heapq import heapify, heappush, heappop
from types import GeneratorType
import sys

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

@bootstrap
def DFS(tree, node, leafs, costs, weights):
	if not tree[node]:
		leafs[node] = 1
		yield 1
	for child in tree[node]:
		tree[child].remove(node)
		if (node, child) in weights:
			costs[child] = weights[node, child]
		else:
			costs[child] = weights[child, node]
		l = (yield DFS(tree, child, leafs, costs, weights))
		leafs[node] += leafs[child]
	yield True

def main():
	t = Iint()
	for _ in range(t):
		(n, s) = Imap()
		tree = [set() for i in range(n + 1)]
		weights = dict()
		for i in range(n - 1):
			(v, u, w) = Imap()
			tree[u].add(v)
			tree[v].add(u)
			weights[u, v] = w
		leafs = [0] * (n + 1)
		costs = [0] * (n + 1)
		DFS(tree, 1, leafs, costs, weights)
		weight_cost = [0] * (n + 1)
		weight_change = [0] * (n + 1)
		total_cost = 0
		for i in range(n + 1):
			weight_cost[i] = costs[i] * leafs[i]
			wc = leafs[i] * (costs[i] - costs[i] // 2)
			weight_change[i] = (-wc, i)
			total_cost += weight_cost[i]
		weight_change = weight_change[2:]
		heapify(weight_change)
		ans = 0
		while total_cost > s:
			ans += 1
			(x, i) = heappop(weight_change)
			if x == 0:
				continue
			total_cost += x
			costs[i] = costs[i] // 2
			wc = leafs[i] * (costs[i] - costs[i] // 2)
			if w != 0:
				heappush(weight_change, (-wc, i))
		print(ans)
FIO = 10

def Iint():
	return int(input())

def Imap():
	return map(int, input().split())
en = enumerate

def console(*args):
	print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)
	return
if not FIO:
	if __name__ == '__main__':
		main()
		exit()
else:
	from io import BytesIO, IOBase
	import os
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def input():
	return sys.stdin.readline().rstrip('\r\n')
try:
	main()
except RecursionError as e:
	pass


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for tests in range(t):
	(n, S) = map(int, input().split())
	E = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(x, y, w) = map(int, input().split())
		E[x].append((y, w))
		E[y].append((x, w))
	Q = [1]
	P = [-1] * (n + 1)
	USE = [0] * (n + 1)
	USE[1] = 1
	TOP_SORT = []
	while Q:
		x = Q.pop()
		TOP_SORT.append(x)
		for (to, w) in E[x]:
			if USE[to] == 0:
				USE[to] = 1
				P[to] = x
				Q.append(to)
	COUNT = [0] * (n + 1)
	for x in TOP_SORT[1:][::-1]:
		if len(E[x]) == 1:
			COUNT[x] = 1
			COUNT[P[x]] += 1
		else:
			COUNT[P[x]] += COUNT[x]
	H = []
	W = 0
	for i in range(2, n + 1):
		for (x, w) in E[i]:
			if x == P[i]:
				W += w * COUNT[i]
				ww = w
				cc = COUNT[i]
				while ww:
					H.append(cc * (ww - ww // 2))
					ww //= 2
	if W <= S:
		print(0)
		continue
	H.sort(reverse=True)
	WH = 0
	for i in range(len(H)):
		WH += H[i]
		if WH >= W - S:
			print(i + 1)
			break


from heapq import *
import sys
data = [list(map(int, text.split())) for text in sys.stdin.readlines()]
line = 1
for _ in range(data[0][0]):
	(n, s) = data[line]
	line += 1
	dic = [[] for _ in range(n + 1)]
	(gress, count, father, W, C) = ([0] * (n + 1), [0] * (n + 1), [0] * (n + 1), [0] * (n + 1), [0] * (n + 1))
	gress[1] = -n - 1
	for (u, v, _, _) in data[line:line + n - 1]:
		dic[u].append(v)
		dic[v].append(u)
		gress[u] += 1
		gress[v] += 1
	leaf = []
	now = [1]
	while now:
		node = now.pop()
		if gress[node] == 1:
			count[node] = 1
			leaf.append(node)
		for child in dic[node]:
			if child != father[node]:
				father[child] = node
				now.append(child)
	for (u, v, w, c) in data[line:line + n - 1]:
		if father[u] == v:
			W[u] = w
			C[u] = c
		elif father[v] == u:
			W[v] = w
			C[v] = c
	(weight1, weight2) = ([], [])
	(n1, n2) = (0, 0)
	while leaf:
		node = leaf.pop()
		f = father[node]
		count[f] += count[node]
		gress[f] -= 1
		if gress[f] == 1:
			leaf.append(f)
		delta = ((W[node] >> 1) - W[node]) * count[node]
		if C[node] == 1:
			n1 += W[node] * count[node]
			weight1.append((delta, node))
		else:
			n2 += W[node] * count[node]
			weight2.append((delta, node))
	heapify(weight1)
	heapify(weight2)
	(v1, v2) = ([n1], [n2])
	(t1, t2) = (max(0, s - n2), max(0, s - n1))
	while n1 > t1:
		(delta, node) = heappop(weight1)
		n1 += delta
		v1.append(n1)
		if W[node] > 1:
			W[node] >>= 1
			heappush(weight1, (((W[node] >> 1) - W[node]) * count[node], node))
	while n2 > t2:
		(delta, node) = heappop(weight2)
		n2 += delta
		v2.append(n2)
		if W[node] > 1:
			W[node] >>= 1
			heappush(weight2, (((W[node] >> 1) - W[node]) * count[node], node))
	res = float('inf')
	j = len(v2) - 1
	for i in range(len(v1)):
		if v1[i] > s:
			continue
		while j > 0 and v1[i] + v2[j - 1] <= s:
			j -= 1
		res = min(res, i + 2 * j)
		if i >= res:
			break
	print(res)
	line += n - 1


from functools import cmp_to_key
from collections import deque
from heapq import heappush, heappop
from math import log, ceil
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def ii():
	return int(inp())

def li(lag=0):
	l = list(map(int, inp().split()))
	if lag != 0:
		for i in range(len(l)):
			l[i] += lag
	return l

def mi(lag=0):
	matrix = list()
	for i in range(n):
		matrix.append(li(lag))
	return matrix

def sli():
	return list(map(str, inp().split()))

def print_list(lista, space=' '):
	print(space.join(map(str, lista)))

class UnionFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def bisect_left(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] < x:
			left = mid + 1
		else:
			right = mid
	return left

def bisect_right(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] > x:
			right = mid
		else:
			left = mid + 1
	return left

def bisect_elements(a, x):
	return bisect_right(a, x) - bisect_left(a, x)

def custom_sort(lista):

	def cmp(x, y):
		if x + y > y + x:
			return 1
		else:
			return -1
	return sorted(lista, key=cmp_to_key(cmp))
MOD = 10 ** 9 + 7
maxN = 10 ** 5
FACT = [0] * maxN

def add(x, y):
	return (x + y) % MOD

def multiply(x, y):
	return x * y % MOD

def power(x, y):
	if y == 0:
		return 1
	elif y % 2:
		return multiply(x, power(x, y - 1))
	else:
		a = power(x, y // 2)
		return multiply(a, a)

def inverse(x):
	return power(x, MOD - 2)

def divide(x, y):
	return multiply(x, inverse(y))

def allFactorials():
	FACT[0] = 1
	for i in range(1, maxN):
		FACT[i] = multiply(i, FACT[i - 1])

def coeffBinom(n, k):
	if n < k:
		return 0
	return divide(FACT[n], multiply(FACT[k], FACT[n - k]))

def primes(N):
	smallest_prime = [1] * (N + 1)
	prime = []
	smallest_prime[0] = 0
	smallest_prime[1] = 0
	for i in range(2, N + 1):
		if smallest_prime[i] == 1:
			prime.append(i)
			smallest_prime[i] = i
		j = 0
		while j < len(prime) and i * prime[j] <= N:
			smallest_prime[i * prime[j]] = min(prime[j], smallest_prime[i])
			j += 1
	return (prime, smallest_prime)

def gcd(a, b):
	a = abs(a)
	b = abs(b)
	(s, t, r) = (0, 1, b)
	(old_s, old_t, old_r) = (1, 0, a)
	while r != 0:
		quotient = old_r // r
		(old_r, r) = (r, old_r - quotient * r)
		(old_s, s) = (s, old_s - quotient * s)
		(old_t, t) = (t, old_t - quotient * t)
	return (old_r, old_s, old_t)

def create_graph(n, m, undirected=1, unweighted=1):
	graph = [[] for i in range(n)]
	if unweighted:
		for i in range(m):
			[x, y] = li(lag=-1)
			graph[x].append(y)
			if undirected:
				graph[y].append(x)
	else:
		for i in range(m):
			[x, y, w] = li(lag=-1)
			w += 1
			graph[x].append([y, w])
			if undirected:
				graph[y].append([x, w])
	return graph

def create_tree(n, unweighted=1):
	children = [[] for i in range(n)]
	if unweighted:
		for i in range(n - 1):
			[x, y] = li(lag=-1)
			children[x].append(y)
			children[y].append(x)
	else:
		for i in range(n - 1):
			[x, y, w] = li(lag=-1)
			w += 1
			children[x].append([y, w])
			children[y].append([x, w])
	return children

def create_edges(m, unweighted=0):
	edges = list()
	if unweighted:
		for i in range(m):
			edges.append(li(lag=-1))
	else:
		for i in range(m):
			[x, y, w] = li(lag=-1)
			w += 1
			edges.append([w, x, y])
	return edges

def dist(tree, n, A, B=-1):
	s = [[A, 0]]
	(massimo, massimo_nodo) = (0, 0)
	distanza = -1
	v = [-1] * n
	while s:
		(el, dis) = s.pop()
		if dis > massimo:
			massimo = dis
			massimo_nodo = el
		if el == B:
			distanza = dis
		for child in tree[el]:
			if v[child] == -1:
				v[child] = 1
				s.append([child, dis + 1])
	return (massimo, massimo_nodo, distanza)

def diameter(tree):
	(_, foglia, _) = dist(tree, n, 0)
	(diam, _, _) = dist(tree, n, foglia)
	return diam

def dfs(graph, n, A):
	v = [-1] * n
	s = [[A, 0]]
	v[A] = 0
	while s:
		(el, dis) = s.pop()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def bfs(graph, n, A):
	v = [-1] * n
	s = deque()
	s.append([A, 0])
	v[A] = 0
	while s:
		(el, dis) = s.popleft()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def connected(graph, n):
	v = dfs(graph, n, 0)
	for el in v:
		if el == -1:
			return False
	return True

def topological(graph, n):
	indegree = [0] * n
	for el in range(n):
		for child in graph[el]:
			indegree[child] += 1
	s = deque()
	for el in range(n):
		if indegree[el] == 0:
			s.append(el)
	order = []
	while s:
		el = s.popleft()
		order.append(el)
		for child in graph[el]:
			indegree[child] -= 1
			if indegree[child] == 0:
				s.append(child)
	if n == len(order):
		return (False, order)
	else:
		return (True, [])

def bipartite(graph, n):
	color = [-1] * n
	color[0] = 0
	s = [0]
	while s:
		el = s.pop()
		for child in graph[el]:
			if color[child] == color[el]:
				return False
			if color[child] == -1:
				s.append(child)
			color[child] = 1 - color[el]
	return True

def dijkstra(graph, n, A):
	dist = [float('inf') for i in range(n)]
	prev = [-1 for i in range(n)]
	dist[A] = 0
	pq = []
	heappush(pq, [0, A])
	while pq:
		[d_v, v] = heappop(pq)
		if d_v != dist[v]:
			continue
		for (to, w) in graph[v]:
			if dist[v] + w < dist[to]:
				dist[to] = dist[v] + w
				prev[to] = v
				heappush(pq, [dist[to], to])
	return (dist, prev)

def dijkstra_0_1(graph, n, A):
	dist = [float('inf') for i in range(n)]
	dist[A] = 0
	p = deque()
	p.append(A)
	while p:
		v = p.popleft()
		for (to, w) in graph[v]:
			if dist[v] + w < dist[to]:
				dist[to] = dist[v] + w
			if w == 1:
				q.append(to)
			else:
				q.appendleft(to)
	return dist

def floyd_warshall(graph, n):
	dist = [[float('inf') for _ in range(n)] for _ in range(n)]
	for i in range(n):
		dist[i][i] = 0
		for (child, d) in graph[i]:
			dist[i][child] = d
			dist[child][i] = d
	for k in range(n):
		for i in range(n):
			for j in range(j):
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
	return dist

def minimum_spanning_tree(edges, n):
	edges = sorted(edges)
	union_find = UnionFind(n)
	used_edges = list()
	for (w, x, y) in edges:
		if union_find.find(x) != union_find.find(y):
			union_find.merge(x, y)
			used_edges.append([w, x, y])
	return used_edges

def parents_children_root_unrooted_tree(tree, n, root=0):
	q = deque()
	visited = [0] * n
	parent = [[-1, -1] for i in range(n)]
	children = [[] for i in range(n)]
	q.append(root)
	while q:
		all_done = 1
		visited[q[0]] = 1
		for (child, x) in tree[q[0]]:
			if not visited[child]:
				all_done = 0
				q.appendleft(child)
		if all_done:
			for (child, x) in tree[q[0]]:
				if parent[child][0] == -1:
					parent[q[0]] = [child, x]
					children[child].append(q[0])
			q.popleft()
	return (parent, children)

def all_longest_path_passing_from_node(parent, children, n):
	q = deque()
	visited = [len(children[i]) for i in range(n)]
	downwards = [[0, 0] for i in range(n)]
	upward = [1] * n
	longest_path = [1] * n
	for i in range(n):
		if not visited[i]:
			q.append(i)
			downwards[i] = [1, 0]
	while q:
		node = q.popleft()
		if parent[node] != -1:
			visited[parent[node]] -= 1
			if not visited[parent[node]]:
				q.append(parent[node])
		else:
			root = node
		for child in children[node]:
			downwards[node] = sorted([downwards[node][0], downwards[node][1], downwards[child][0] + 1], reverse=True)[0:2]
	s = [node]
	while s:
		node = s.pop()
		if parent[node] != -1:
			if downwards[parent[node]][0] == downwards[node][0] + 1:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][1])
			else:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][0])
		longest_path[node] = downwards[node][0] + downwards[node][1] + upward[node] - min([downwards[node][0], downwards[node][1], upward[node]]) - 1
		for child in children[node]:
			s.append(child)
	return longest_path

def finding_ancestors(parent, queries, n):
	steps = int(ceil(log(n, 2)))
	ancestors = [[-1 for i in range(n)] for j in range(steps)]
	ancestors[0] = parent
	for i in range(1, steps):
		for node in range(n):
			if ancestors[i - 1][node] != -1:
				ancestors[i][node] = ancestors[i - 1][ancestors[i - 1][node]]
	result = []
	for (node, k) in queries:
		ans = node
		if k >= n:
			ans = -1
		i = 0
		while k > 0 and ans != -1:
			if k % 2:
				ans = ancestors[i][ans]
			k = k // 2
			i += 1
		result.append(ans)
	return result

def prefix_sum(arr):
	r = [0] * (len(arr) + 1)
	for (i, el) in enumerate(arr):
		r[i + 1] = r[i] + el
	return r

def nearest_from_the_left_smaller_elements(arr):
	n = len(arr)
	res = [-1] * n
	s = []
	for (i, el) in enumerate(arr):
		while s and s[-1] >= el:
			s.pop()
		if s:
			res[i] = s[-1]
		s.append(el)
	return res

def sliding_window_minimum(arr, k):
	res = []
	q = deque()
	for (i, el) in enumerate(arr):
		while q and arr[q[-1]] >= el:
			q.pop()
		q.append(i)
		while q and q[0] <= i - k:
			q.popleft()
		if i >= k - 1:
			res.append(arr[q[0]])
	return res
from heapq import heapify

def f(w, n):
	return n * w - n * (w // 2)
for test in range(ii()):
	(n, so) = li()
	tree = create_tree(n, 0)
	parent = [-1] * n
	parent[0] = -2
	peso = [-1] * n
	indegree = [0] * n
	dp = [0] * n
	s = [0]
	while s:
		el = s.pop()
		for (child, w) in tree[el]:
			if parent[child] == -1:
				parent[child] = el
				peso[child] = w
				indegree[el] += 1
				s.append(child)
	parent[0] = -1
	q = deque()
	for el in range(n):
		if indegree[el] == 0:
			dp[el] = 1
			q.append(el)
	pesi = []
	somma = 0
	while q:
		el = q.popleft()
		if parent[el] != -1:
			dp[parent[el]] += dp[el]
			if indegree[parent[el]] == 1:
				q.append(parent[el])
			indegree[parent[el]] -= 1
			pesi.append([-f(peso[el], dp[el]), dp[el], peso[el]])
			somma += dp[el] * peso[el]
	mosse = 0
	pesih = []
	for el in pesi:
		heappush(pesih, el)
	while somma > so:
		(_, n, w) = heappop(pesih)
		somma -= f(w, n)
		mosse += 1
		w = w // 2
		while w * n > so:
			somma -= f(w, n)
			mosse += 1
			w = w // 2
		heappush(pesih, [-f(w, n), n, w])
	print(mosse)


import io
import os
import heapq
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_str():
	return input().decode().strip()

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

def oint():
	return int(input())

def dfs(cur):
	stack = [cur]
	while stack:
		cur = stack[-1]
		if v[cur] == 0:
			v[cur] = 1
			for (ni, nw, _) in adj[cur]:
				if v[ni]:
					continue
				stack.append(ni)
		else:
			if cur != 1 and len(adj[cur]) == 1:
				ret = 1
			else:
				ret = 0
			for (ni, nw, cc) in adj[cur]:
				if v[ni] == 1:
					w[cur] = nw
					c[cur] = cc
					continue
				ret += lc[ni]
			lc[cur] = ret
			if c[cur] == 1:
				if w[cur]:
					sl1.append((lc[cur] * (w[cur] // 2) - lc[cur] * w[cur], cur))
			elif w[cur]:
				sl2.append((lc[cur] * (w[cur] // 2) - lc[cur] * w[cur], cur))
			v[cur] = 2
			stack.pop()
t = oint()
for _ in range(t):
	(n, s) = rint()
	adj = [[] for i in range(n + 1)]
	v = [0] * (n + 1)
	lc = [0] * (n + 1)
	w = [0] * (n + 1)
	c = [1] * (n + 1)
	sl1 = []
	sl2 = []
	for i in range(n - 1):
		(vv, uu, ww, cc) = rint()
		adj[vv].append((uu, ww, cc))
		adj[uu].append((vv, ww, cc))
	dfs(1)
	sum_ = 0
	for item in sl1:
		i = item[1]
		mul = lc[i]
		sum_ += mul * w[i]
	for item in sl2:
		i = item[1]
		mul = lc[i]
		sum_ += mul * w[i]
	heapq.heapify(sl1)
	heapq.heapify(sl2)
	cost = 0
	while sum_ > s:
		if not sl1:
			item = heapq.heappop(sl2)
			i = item[1]
			mul = lc[i]
			cost += 2
			sum_ = sum_ + item[0]
			w[i] //= 2
			if w[i] != 0:
				heapq.heappush(sl2, (mul * (w[i] // 2) - mul * w[i], i))
			continue
		if not sl2:
			item = heapq.heappop(sl1)
			i = item[1]
			mul = lc[i]
			cost += 1
			sum_ = sum_ + item[0]
			w[i] //= 2
			if w[i] != 0 or len(sl1) == 0:
				heapq.heappush(sl1, (mul * (w[i] // 2) - mul * w[i], i))
			continue
		if sl1[0][0] + sum_ <= s:
			cost += 1
			break
		if sl2[0][0] + sum_ <= s:
			cost += 2
			break
		item1 = heapq.heappop(sl1)
		i = item1[1]
		mul = lc[i]
		diff2 = mul * (w[i] // 2 // 2) - mul * (w[i] // 2)
		if sl1:
			diff = min(diff2, sl1[0][0])
		else:
			diff = diff2
		item2 = sl2[0]
		if item2[0] < item1[0] + diff:
			cost += 2
			heapq.heappush(sl1, item1)
			i = item2[1]
			mul = lc[i]
			sum_ = sum_ + item2[0]
			w[i] //= 2
			heapq.heappop(sl2)
			if w[i] != 0:
				heapq.heappush(sl2, (mul * (w[i] // 2) - mul * w[i], i))
		else:
			cost += 1
			sum_ = sum_ + item1[0]
			w[i] //= 2
			if w[i] != 0:
				heapq.heappush(sl1, (diff2, i))
	print(cost)


from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
import sys
input = sys.stdin.buffer.readline

def getChange(wt, cnt):
	return (wt - wt // 2) * cnt
t = int(input())
for _ in range(t):
	(n, S) = [int(x) for x in input().split()]
	adj = [[] for _ in range(n + 1)]
	for j in range(n - 1):
		(u, v, w) = [int(x) for x in input().split()]
		adj[u].append([v, w])
		adj[v].append([u, w])

	@bootstrap
	def dfs(node, parent, wt):
		nextNodes = []
		for (ne, w) in adj[node]:
			if ne != parent:
				nextNodes.append([ne, w])
		if len(nextNodes) == 0:
			totalWt[0] += wt
			yield 1
		else:
			leafCount = 0
			for (ne, w) in nextNodes:
				leafCountSubtree = (yield dfs(ne, node, w + wt))
				leafCount += leafCountSubtree
				while w > 0:
					changeValues.append(leafCountSubtree * (w - w // 2))
					w //= 2
			yield leafCount
	changeValues = []
	totalWt = [0]
	dfs(1, 0, 0)
	changeValues.sort(reverse=True)
	diff = totalWt[0] - S
	cnts = 0
	for x in changeValues:
		if diff <= 0:
			break
		diff -= x
		cnts += 1
	print(cnts)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

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

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

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
from heapq import *
import bisect as bs
from collections import defaultdict as dc
for _ in range(N()):
	(n, s) = RL()
	edges = [RLL() for _ in range(n - 1)]
	dic = [[] for _ in range(n + 1)]
	gress = [0] * (n + 1)
	gress[1] = -n - 1
	for (u, v, _, _) in edges:
		dic[u].append(v)
		dic[v].append(u)
		gress[u] += 1
		gress[v] += 1
	leaf = []
	count = [0] * (n + 1)
	for i in range(2, n + 1):
		if gress[i] == 1:
			leaf.append(i)
			count[i] = 1
	father = [0] * (n + 1)
	now = [1]
	while now:
		node = now.pop()
		for child in dic[node]:
			if child != father[node]:
				father[child] = node
				now.append(child)
	W = [0] * (n + 1)
	C = [0] * (n + 1)
	for (u, v, w, c) in edges:
		if father[u] == v:
			W[u] = w
			C[u] = c
		elif father[v] == u:
			W[v] = w
			C[v] = c
	weight1 = []
	weight2 = []
	(n1, n2) = (0, 0)
	while leaf:
		node = leaf.pop()
		f = father[node]
		count[f] += count[node]
		gress[f] -= 1
		if gress[f] == 1:
			leaf.append(f)
		d = W[node] * count[node]
		dd = ((W[node] >> 1) - W[node]) * count[node]
		if C[node] == 1:
			n1 += d
			weight1.append((dd, node))
		else:
			n2 += d
			weight2.append((dd, node))
	heapify(weight1)
	heapify(weight2)
	(v1, v2) = ([n1], [n2])
	t1 = max(0, s - n2)
	t2 = max(0, s - n1)
	while n1 > t1:
		(delta, node) = heappop(weight1)
		n1 += delta
		v1.append(n1)
		if W[node] > 1:
			W[node] >>= 1
			heappush(weight1, (((W[node] >> 1) - W[node]) * count[node], node))
	while n2 > t2:
		(delta, node) = heappop(weight2)
		n2 += delta
		v2.append(n2)
		if W[node] > 1:
			W[node] >>= 1
			heappush(weight2, (((W[node] >> 1) - W[node]) * count[node], node))
	res = float('inf')
	j = len(v2) - 1
	for i in range(len(v1)):
		if v1[i] > s:
			continue
		while j > 0 and v1[i] + v2[j - 1] <= s:
			j -= 1
		res = min(res, i + 2 * j)
		if i >= res:
			break
	print(res)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

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

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

def ws(s):
	sys.stdout.write(s)
	sys.stdout.write('\n')

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

def wia(a, sep=' '):
	sys.stdout.write(sep.join([str(x) for x in a]))
	sys.stdout.write('\n')
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
import heapq
from collections import deque

def solve(n, s, g, e):
	parent = [-1] * n
	cnt = [0] * n

	@bootstrap
	def dfs(v, p=-1):
		for w in g[v]:
			if w[0] == p:
				continue
			parent[w[0]] = v
			yield dfs(w[0], v)
			cnt[v] += cnt[w[0]]
		if len(g[v]) == 1:
			cnt[v] += 1
		yield
	dfs(0)
	ss = 0
	q = []
	for (u, v, w) in e:
		x = cnt[u] if parent[u] == v else cnt[v]
		ss += w * x
		ww = w
		while True:
			delta = x * (ww - ww // 2)
			if delta > 0:
				q.append(delta)
				ww //= 2
			else:
				break
	ans = 0
	q.sort()
	while ss > s:
		ss -= q[-1]
		q.pop()
		ans += 1
	return ans

def main():
	for _ in range(ri()):
		(n, s) = ria()
		g = [[] for i in range(n)]
		e = []
		for i in range(n - 1):
			(u, v, w) = ria()
			u -= 1
			v -= 1
			g[u].append((v, w))
			g[v].append((u, w))
			e.append((u, v, w))
		wi(solve(n, s, g, e))

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


import sys, heapq
input = sys.stdin.buffer.readline
t = 1
t = int(input())
for _ in range(t):
	(n, S) = map(int, input().split())
	edge = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		edge[u - 1].append((v - 1, w))
		edge[v - 1].append((u - 1, w))
	que = [0]
	ans = []
	parent = [-1] * n
	while que:
		next = []
		while que:
			v = que.pop()
			ans.append(v)
			for (nv, w) in edge[v]:
				if nv != parent[v]:
					parent[nv] = v
					next.append(nv)
		que = next
	for v in range(n):
		edge[v] = [edge[v][i] for i in range(len(edge[v])) if edge[v][i][0] != parent[v]]
	size = [0] * n
	ans = ans[::-1]
	for v in ans:
		for (nv, w) in edge[v]:
			size[v] += size[nv]
		if len(edge[v]) == 0:
			size[v] = 1
	s = 0
	que = []
	for v in range(n):
		for (nv, w) in edge[v]:
			s += size[nv] * w
			while True:
				minus = size[nv] * (w - w // 2)
				if minus > 0:
					que.append(minus)
					w //= 2
				else:
					break
	que.sort()
	count = 0
	while s > S:
		s -= que[-1]
		que.pop()
		count += 1
	print(count)


import sys, bisect, string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, groupby
rep = range
R = range

def Golf():
	(n, *t) = map(int, open(0).read().split())

def I():
	return int(input())

def S_():
	return input()

def IS():
	return input().split()

def LS():
	return [i for i in input().split()]

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

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def NI(n):
	return [int(input()) for i in range(n)]

def NI_(n):
	return [int(input()) - 1 for i in range(n)]

def StoLI():
	return [ord(i) - 97 for i in input()]

def ItoS(n):
	return chr(n + 97)

def LtoS(ls):
	return ''.join([chr(i + 97) for i in ls])

def Ra():
	return map(int, open(0).read().split())

def GI(V, E, ls=None, Directed=False, index=1):
	org_inp = []
	g = [[] for i in range(V)]
	FromStdin = True if ls == None else False
	for i in range(E):
		if FromStdin:
			inp = LI()
			org_inp.append(inp)
		else:
			inp = ls[i]
		if len(inp) == 2:
			(a, b) = inp
			c = 1
		else:
			(a, b, c) = inp
		if index == 1:
			a -= 1
			b -= 1
		aa = (a, c)
		bb = (b, c)
		g[a].append(bb)
		if not Directed:
			g[b].append(aa)
	return (g, org_inp)

def GGI(h, w, search=None, replacement_of_found='.', mp_def={'#': 1, '.': 0}, boundary=1):
	mp = [boundary] * (w + 2)
	found = {}
	for i in R(h):
		s = input()
		for char in search:
			if char in s:
				found[char] = (i + 1) * (w + 2) + s.index(char) + 1
				mp_def[char] = mp_def[replacement_of_found]
		mp += [boundary] + [mp_def[j] for j in s] + [boundary]
	mp += [boundary] * (w + 2)
	return (h + 2, w + 2, mp, found)

def TI(n):
	return GI(n, n - 1)

def accum(ls):
	rt = [0]
	for i in ls:
		rt += [rt[-1] + i]
	return rt

def bit_combination(n, base=2):
	rt = []
	for tb in R(base ** n):
		s = [tb // base ** bt % base for bt in R(n)]
		rt += [s]
	return rt

def gcd(x, y):
	if y == 0:
		return x
	if x % y == 0:
		return y
	while x % y != 0:
		(x, y) = (y, x % y)
	return y

def YN(x):
	print(['NO', 'YES'][x])

def Yn(x):
	print(['No', 'Yes'][x])

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
mo = 10 ** 9 + 7
inf = float('inf')
FourNb = [(-1, 0), (1, 0), (0, 1), (0, -1)]
EightNb = [(-1, 0), (1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
compas = dict(zip('WENS', FourNb))
cursol = dict(zip('LRUD', FourNb))
l_alp = string.ascii_lowercase
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
input = lambda : sys.stdin.readline().rstrip()
import sys, bisect, string, math, time, functools, random, fractions
from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
from itertools import permutations, combinations, groupby
rep = range

def Golf():
	(n, *t) = map(int, open(0).read().split())

def I():
	return int(input())

def S_():
	return input()

def IS():
	return input().split()

def LS():
	return [i for i in input().split()]

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

def LI():
	return [int(i) for i in input().split()]

def LI_():
	return [int(i) - 1 for i in input().split()]

def NI(n):
	return [int(input()) for i in range(n)]

def NI_(n):
	return [int(input()) - 1 for i in range(n)]

def StoLI():
	return [ord(i) - 97 for i in input()]

def ItoS(n):
	return chr(n + 97)

def LtoS(ls):
	return ''.join([chr(i + 97) for i in ls])

def RA():
	return map(int, open(0).read().split())

def GI(V, E, ls=None, Directed=False, index=1):
	org_inp = []
	g = [[] for i in range(V)]
	FromStdin = True if ls == None else False
	for i in range(E):
		if FromStdin:
			inp = LI()
			org_inp.append(inp)
		else:
			inp = ls[i]
		if len(inp) == 2:
			(a, b) = inp
			c = 1
		else:
			(a, b, c) = inp
		if index == 1:
			a -= 1
			b -= 1
		aa = (a, c)
		bb = (b, c)
		g[a].append(bb)
		if not Directed:
			g[b].append(aa)
	return (g, org_inp)

def GGI(h, w, search=None, replacement_of_found='.', mp_def={'#': 1, '.': 0}, boundary=1):
	mp = [boundary] * (w + 2)
	found = {}
	for i in range(h):
		s = input()
		for char in search:
			if char in s:
				found[char] = (i + 1) * (w + 2) + s.index(char) + 1
				mp_def[char] = mp_def[replacement_of_found]
		mp += [boundary] + [mp_def[j] for j in s] + [boundary]
	mp += [boundary] * (w + 2)
	return (h + 2, w + 2, mp, found)

def TI(n):
	return GI(n, n - 1)

def accum(ls):
	rt = [0]
	for i in ls:
		rt += [rt[-1] + i]
	return rt

def bit_combination(n, base=2):
	rt = []
	for tb in range(base ** n):
		s = [tb // base ** bt % base for bt in range(n)]
		rt += [s]
	return rt

def gcd(x, y):
	if y == 0:
		return x
	if x % y == 0:
		return y
	while x % y != 0:
		(x, y) = (y, x % y)
	return y

def YN(x):
	print(['NO', 'YES'][x])

def Yn(x):
	print(['No', 'Yes'][x])

def show(*inp, end='\n'):
	if show_flg:
		print(*inp, end=end)
mo = 10 ** 9 + 7
inf = float('inf')
FourNb = [(-1, 0), (1, 0), (0, 1), (0, -1)]
EightNb = [(-1, 0), (1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (1, -1), (-1, 1)]
compas = dict(zip('WENS', FourNb))
cursol = dict(zip('LRUD', FourNb))
l_alp = string.ascii_lowercase
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
input = lambda : sys.stdin.readline().rstrip()

class Tree:

	def __init__(self, inp_size=None, ls=None, init=True, index=1):
		self.LCA_init_stat = False
		self.ETtable = []
		if init:
			if ls == None:
				self.stdin(inp_size, index=index)
			else:
				self.node_size = len(ls) + 1
				(self.edges, self.orgin) = GI(self.node_size, self.node_size - 1, ls, index=index)
		return

	def stdin(self, inp_size=None, index=1):
		if inp_size == None:
			self.node_size = int(input())
		else:
			self.node_size = inp_size
		(self.edges, self.orgin) = GI(self.node_size, self.node_size - 1, index=index)
		return

	def listin(self, ls, index=0):
		self.node_size = len(ls) + 1
		(self.edges, self.orgin) = GI(self.node_size, self.node_size - 1, ls, index=index)
		return

	def dfs(self, x, func=lambda pr, prv, nx, dist: prv + dist, root_v=0):
		q = deque([x])
		v = [None] * self.node_size
		v[x] = root_v
		while q:
			c = q.pop()
			for (nb, d) in self.edges[c]:
				if v[nb] == None:
					q.append(nb)
					v[nb] = func(c, v[c], nb, d)
		return v

	def bfs(self, x, func=lambda pr, prv, nx, dist: prv + dist, root_v=0):
		q = deque([x])
		v = [None] * self.node_size
		v[x] = root_v
		while q:
			c = q.popleft()
			for (nb, d) in self.edges[c]:
				if v[nb] == None:
					q.append(nb)
					v[nb] = func(c, v[c], nb, d)
		return v

	def parent(self, x):
		return self.dfs(0, func=lambda pr, prv, nx, dist: pr, root_v=-1)

	def topological_sort(self, x):
		tps = []
		q = deque([x])
		v = [None] * self.node_size
		v[x] = 0
		while q:
			c = q.popleft()
			tps.append(c)
			for (nb, d) in self.edges[c]:
				if v[nb] == None:
					q.append(nb)
					v[nb] = 0
		return tps

	def EulerTour(self, x):
		q = deque()
		q.append(x)
		self.depth = [None] * self.node_size
		self.depth[x] = 0
		self.ETtable = []
		self.ETdepth = []
		self.ETin = [-1] * self.node_size
		self.ETout = [-1] * self.node_size
		cnt = 0
		while q:
			c = q.pop()
			if c < 0:
				ce = ~c
			else:
				ce = c
				for (nb, d) in self.edges[ce]:
					if self.depth[nb] == None:
						q.append(~ce)
						q.append(nb)
						self.depth[nb] = self.depth[ce] + 1
			self.ETtable.append(ce)
			self.ETdepth.append(self.depth[ce])
			if self.ETin[ce] == -1:
				self.ETin[ce] = cnt
			else:
				self.ETout[ce] = cnt
			cnt += 1
		return

	def doubling_LCA(self, root, x, y):
		if self.LCA_init_stat == False:
			self.depth = [None] * self.node_size
			self.depth = self.bfs(0, func=lambda pr, prv, nxt, dist: prv + 1)
			self.par = self.bfs(0, func=lambda pr, prv, nxt, dist: pr)
			self.db = [self.par]
			for i in range(self.node_size.bit_length()):
				self.db += [[self.db[-1][self.db[-1][i]] for i in range(self.node_size)]]
			self.LCA_init_stat = True
		dx = self.depth[x]
		dy = self.depth[y]
		if dx > dy:
			(dx, dy) = (dy, dx)
		c = self.node_size.bit_length()
		while c > 0:
			if dx + c <= dy:
				x = self.db[c][x]
				dx += 1 << c
			c >>= 1
		if x == y:
			return x
		c = self.node_size.bit_length()
		while c > 0:
			if self.db[c][x] != self.db[c][y]:
				x = self.db[c][x]
				y = self.db[c][y]
			c >>= 1
		return self.par[x]

	def LCA_init(self, root):
		self.EulerTour(root)
		self.st = SparseTable(self.ETdepth, init_func=min, init_idl=inf)
		self.LCA_init_stat = True
		return

	def LCA(self, root, x, y):
		if self.LCA_init_stat == False:
			self.LCA_init(root)
		(xin, xout) = (self.ETin[x], self.ETout[x])
		(yin, yout) = (self.ETin[y], self.ETout[y])
		a = min(xin, yin)
		b = max(xout, yout, xin, yin)
		id_of_min_dep_in_et = self.st.query_id(a, b + 1)
		return self.ETtable[id_of_min_dep_in_et]

	def __str__(self):
		return str(self.edges)

	def show(self):
		if all([all([d == 1 for (nd, d) in e]) for e in self.edges]):
			print([[nd for (nd, d) in e] for e in self.edges])
		else:
			print(self)

	def dfs2(self, x, func=lambda pr, prv, nx, dist: prv + dist, root_v=0):
		q = deque([x])
		v = [None] * self.node_size
		v[x] = root_v
		dfs_tr = [x]
		while q:
			c = q.pop()
			for (nb, d) in self.edges[c]:
				if v[nb] == None:
					q.append(nb)
					v[nb] = func(c, v[c], nb, d)
					dfs_tr += (nb,)
		return (v, dfs_tr)
show_flg = False
show_flg = True
ans = 0
for _ in range(I()):
	ans = 0
	(n, s) = LI()
	tr = Tree(n)
	p = tr.parent(0)
	(v, dfs_tr) = tr.dfs2(0)
	lf = [0] * n
	for i in dfs_tr[::-1]:
		if lf[i] == 0:
			lf[i] = 1
		if p[i] != -1:
			lf[p[i]] += lf[i]
	q = []
	d = 0
	for (u, v, w) in tr.orgin:
		u -= 1
		v -= 1
		if p[u] == v:
			heappush(q, (-(w - w // 2) * lf[u], (lf[u], w)))
			d += w * lf[u]
		else:
			heappush(q, (-(w - w // 2) * lf[v], (lf[v], w)))
			d += w * lf[v]
	while d > s:
		ans += 1
		(c, (l, w)) = heappop(q)
		d += c
		w = w // 2
		heappush(q, (-(w - w // 2) * l, (l, w)))
	print(ans)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

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

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

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

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]
from heapq import *
for _ in range(II()):
	(n, s) = MI()
	to = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v, w) = MI()
		to[u - 1].append((v - 1, w))
		to[v - 1].append((u - 1, w))
	ln = [-1] * n
	hp = []
	tot = 0
	ans = 0
	stack = [(0, -1)]
	while stack:
		(u, pu) = stack.pop()
		if ln[u] == -1:
			ln[u] = 0
			stack.append((u, pu))
			for (v, w) in to[u]:
				if v == pu:
					continue
				stack.append((v, u))
		elif u and len(to[u]) == 1:
			ln[u] = 1
		else:
			res = 0
			for (v, w) in to[u]:
				if v == pu:
					continue
				ln[u] += ln[v]
				while w * ln[v] > s:
					w >>= 1
					ans += 1
				heappush(hp, (-((w + 1) // 2 * ln[v]), w, ln[v]))
				tot += w * ln[v]
	while tot > s:
		(d, w, p) = heappop(hp)
		ans += 1
		tot += d
		w //= 2
		heappush(hp, (-((w + 1) // 2 * p), w, p))
	print(ans)


import sys, bisect
from collections import deque
input = sys.stdin.buffer.readline
t = 1
t = int(input())
for _ in range(t):
	(n, S) = map(int, input().split())
	edge = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v, w, c) = map(int, input().split())
		edge[u - 1].append((v - 1, w, float(c)))
		edge[v - 1].append((u - 1, w, float(c)))
	ans = [0]
	deq = deque(ans)
	parent = [-1] * n
	while deq:
		v = deq.popleft()
		for (nv, w, c) in edge[v]:
			if nv != parent[v]:
				parent[nv] = v
				ans.append(nv)
				deq.append(nv)
	for v in range(n):
		edge[v] = [edge[v][i] for i in range(len(edge[v])) if edge[v][i][0] != parent[v]]
	size = [0] * n
	ans = ans[::-1]
	for v in ans:
		for (nv, w, c) in edge[v]:
			size[v] += size[nv]
		if len(edge[v]) == 0:
			size[v] = 1
	s = 0
	que1 = []
	que2 = []
	for v in range(n):
		for (nv, w, c) in edge[v]:
			s += size[nv] * w
			if c == 1:
				while w >= 1:
					minus = size[nv] * (w - w // 2)
					w //= 2
					que1.append(minus)
			else:
				while w >= 1:
					minus = size[nv] * (w - w // 2)
					w //= 2
					que2.append(minus)
	que1.sort(reverse=True)
	que2.sort(reverse=True)
	(n, m) = (len(que1), len(que2))
	for i in range(1, m):
		que2[i] += que2[i - 1]
	que2 = [0] + que2
	que1 = [0] + que1
	ans = 10 ** 20
	id = m + 1
	cum = 0
	for i in range(n + 1):
		test = i
		cum += que1[i]
		while id > 0 and que2[id - 1] >= s - S - cum:
			id -= 1
		if id != m + 1:
			test += 2 * id
			ans = min(ans, test)
	print(int(ans))


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
from collections import defaultdict
t = int(input())
for ii in range(t):
	graph = defaultdict(list)
	weight = dict()
	(n, s) = map(int, input().split())
	for i in range(n - 1):
		(v, u, w) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
		weight[min(u, v), max(u, v)] = w
	(contrib, leafcount, total) = ([], [0] * (n + 1), 0)
	OBSERVE = 0
	CHECK = 1
	stack = [(OBSERVE, 1, 0)]
	while len(stack):
		(state, vertex, parent) = stack.pop()
		if state == OBSERVE:
			stack.append((CHECK, vertex, parent))
			for child in graph[vertex]:
				if child != parent:
					stack.append((OBSERVE, child, vertex))
		else:
			if len(graph[vertex]) == 1:
				leafcount[vertex] = 1
			for child in graph[vertex]:
				if child != parent:
					leafcount[vertex] += leafcount[child]
					total += weight[min(vertex, child), max(vertex, child)] * leafcount[child]
					weigh = weight[min(vertex, child), max(vertex, child)]
					while weigh:
						contrib.append(leafcount[child] * (weigh - weigh // 2))
						weigh //= 2
	if s >= total:
		print(0)
		continue
	contrib.sort(reverse=True)
	diff = 0
	for i in range(len(contrib)):
		if total - contrib[i] <= s:
			print(i + 1)
			break
		total -= contrib[i]


import sys, threading
from math import inf
input = sys.stdin.readline

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

def dfs(tree, i, sum, p):
	if len(tree[i]) == 1 and i != 0:
		return 1
	cnt = 0
	for (j, w, c) in tree[i]:
		if j != p:
			z = dfs(tree, j, sum + w, i)
			cnt += z
			if c == 1:
				one.append((w, z))
			else:
				two.append((w, z))
	return cnt

def solve():
	t = int(input())
	for _ in range(t):
		(n, w) = put()
		tree = [[] for i in range(n)]
		for i in range(n - 1):
			(x, y, z, c) = put()
			(x, y) = (x - 1, y - 1)
			tree[x].append((y, z, c))
			tree[y].append((x, z, c))
		dfs(tree, 0, 0, -1)
		(s, flag) = (0, True)
		(diffone, difftwo) = ([], [])
		for arr in [one, two]:
			for i in range(len(arr)):
				s += arr[i][0] * arr[i][1]
			while arr:
				(i, j) = arr.pop()
				while i > 0:
					if flag:
						diffone.append((i - i // 2) * j)
					else:
						difftwo.append((i - i // 2) * j)
					i //= 2
			flag = False
		diffone.sort(reverse=True)
		difftwo.sort(reverse=True)
		(s, cnt) = (s - w, inf)
		for i in difftwo:
			s -= i
		(p, q) = (len(diffone), len(difftwo))
		(i, j) = (q - 1, 0)
		while i >= -1:
			while s > 0 and j < p:
				s -= diffone[j]
				j += 1
			if s <= 0:
				cnt = min(cnt, 2 * i + j + 2)
			if i > -1:
				s += difftwo[i]
			i -= 1
		print(cnt)
(one, two) = ([], [])
max_recur_size = 10 ** 5 * 2 + 1000
max_stack_size = max_recur_size * 500
sys.setrecursionlimit(max_recur_size)
threading.stack_size(max_stack_size)
thread = threading.Thread(target=solve)
thread.start()


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
from decimal import Decimal
from fractions import Fraction
INF = float('inf')
mod = int(1000000000.0) + 7

def dfs(graph, start=0):
	n = len(graph)
	dp = [0] * n
	(visited, finished) = ([False] * n, [False] * n)
	stack = [start]
	while stack:
		start = stack[-1]
		if not visited[start]:
			visited[start] = True
			for (child, w) in graph[start]:
				if not visited[child]:
					stack.append(child)
		else:
			stack.pop()
			if len(graph[start]) == 1 and start != 0:
				dp[start] += 1
			for (child, w) in graph[start]:
				if finished[child]:
					dp[start] += dp[child]
			finished[start] = True
	return dp
for t in range(int(data())):
	(n, s1) = mdata()
	g = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v, w) = mdata()
		g[u - 1].append((v - 1, w))
		g[v - 1].append((u - 1, w))
	dp = dfs(g, 0)
	q = []
	s = [0]
	vis = [0] * n
	sum1 = 0
	v = [0] * n
	while s:
		a = s.pop()
		vis[a] = 1
		for (i, w) in g[a]:
			if vis[i] == 0:
				s.append(i)
				heappush(q, ((w // 2 - w) * dp[i], i))
				sum1 += w * dp[i]
				v[i] = w
	cnt = 0
	while sum1 > s1:
		(a, i) = heappop(q)
		sum1 += a
		v[i] //= 2
		w = v[i]
		a = (w // 2 - w) * dp[i]
		heappush(q, ((w // 2 - w) * dp[i], i))
		cnt += 1
	out(cnt)


from collections import deque
import io
import os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
t = int(input())
for _ in range(t):
	(n, s) = map(int, input().split())
	g = [[] for _ in range(n)]
	for _ in range(n - 1):
		(v, u, w) = map(int, input().split())
		u -= 1
		v -= 1
		g[v].append([u, w])
		g[u].append([v, w])
	stack = deque([0])
	visited = [0 for _ in range(n)]
	leafs = [0 for _ in range(n)]
	parent = [0 for _ in range(n)]
	while stack:
		node = stack[-1]
		if not visited[node]:
			visited[node] = 1
			for neighbour in g[node]:
				if neighbour[0] != parent[node]:
					parent[neighbour[0]] = node
					stack.append(neighbour[0])
		else:
			if len(g[node]) == 1:
				leafs[node] = 1
			else:
				for neighbor in g[node]:
					leafs[node] += leafs[neighbor[0]]
			stack.pop()
	delta = []
	total = 0
	for u in range(n):
		for v in g[u]:
			if v[0] == parent[u]:
				total += v[1] * leafs[u]
				w = v[1]
				while w:
					new_w = w // 2
					delta.append((w - new_w) * leafs[u])
					w = new_w
	delta.sort(reverse=True)
	moves = 0
	while total > s:
		total -= delta[moves]
		moves += 1
	print(moves)


import os
import sys
from io import BytesIO, IOBase

def dfs(adj, start=1):
	n = len(adj)
	visited = [False] * n
	srt = [start]
	parent = [-1] * n
	dp = [0] * n
	edge_value = {}
	while srt:
		v = srt.pop()
		if visited[v]:
			if parent[v] != -1:
				(S, w) = parent[v]
				dp[S] += dp[v]
				if (v, S) not in edge_value:
					edge_value[v, S] = [w, 0]
				edge_value[v, S][1] += dp[v]
				dp[v] = 0
			continue
		visited[v] = True
		if parent[v] != -1:
			srt.append(parent[v][0])
		count_child = 0
		for (u, w) in adj[v]:
			if not visited[u]:
				count_child = 1
				parent[u] = [v, w]
				srt.append(u)
		if count_child == 0:
			dp[v] = 1
		if parent[v] != -1:
			(S, w) = parent[v]
			dp[S] += dp[v]
			if (v, S) not in edge_value:
				edge_value[v, S] = [w, 0]
			edge_value[v, S][1] += dp[v]
		dp[v] = 0
	return list(edge_value.values())
import heapq as hq

def main():
	T = iin()
	while T:
		T -= 1
		(n, S) = lin()
		adj = [[] for i in range(n + 1)]
		for _ in range(n - 1):
			(i, j, w) = lin()
			adj[i].append([j, w])
			adj[j].append([i, w])
		edge_val = dfs(adj)
		Q = 0
		ans = []
		for (w, num) in edge_val:
			x = w
			while x:
				ans.append(x * num - x // 2 * num)
				x //= 2
		ans.sort()
		sm = sum([w * num for (w, num) in edge_val])
		while sm > S and ans:
			val = ans.pop()
			sm -= val
			Q += 1
		print(Q)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def iin():
	return int(input())

def lin():
	return list(map(int, input().split()))
main()


from collections import *
from sys import stdin, stdout
input = stdin.buffer.readline
print = stdout.write

def ri():
	return int(input())

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

def topo_sort(tree, root, n):
	visited = [False] * (n + 1)
	visited[root] = True
	stack = [root]
	result = [root]
	while stack:
		u = stack.pop()
		for v in tree[u]:
			if visited[v] == False:
				visited[v] = True
				result.append(v)
				stack.append(v)
	return result[::-1]
t = ri()
for _ in range(t):
	(n, S) = rl()
	edges = []
	for i in range(n - 1):
		edges.append(rl())
	tree = defaultdict(list)
	for (u, v, w_) in edges:
		tree[u].append(v)
		tree[v].append(u)
	root = 1
	topo = topo_sort(tree, root, n)
	cnt = [-1] * (n + 1)
	for u in topo:
		this_cnt = 0
		for v in tree[u]:
			if cnt[v] != -1:
				this_cnt += cnt[v]
		cnt[u] = this_cnt
		if cnt[u] == 0:
			cnt[u] = 1
	gains = []
	sum_weights = 0
	for (child, parent, weight) in edges:
		if cnt[child] > cnt[parent]:
			(child, parent) = (parent, child)
		sum_weights += weight * cnt[child]
		count = cnt[child]
		gain = count * (weight - weight // 2)
		while gain > 0:
			gains.append(gain)
			weight = weight // 2
			gain = count * (weight - weight // 2)
	gains.sort(reverse=True)
	ans = 0
	idx = -1
	while sum_weights > S:
		ans += 1
		idx += 1
		sum_weights -= gains[idx]
	print(str(ans) + '\n')


import sys

def rs():
	return sys.stdin.readline().rstrip()

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

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

def ws(s):
	sys.stdout.write(s)
	sys.stdout.write('\n')

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

def wia(a, sep=' '):
	sys.stdout.write(sep.join([str(x) for x in a]))
	sys.stdout.write('\n')
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
import heapq
from collections import deque

def solve(n, s, g, e):
	top_sorted = []
	parent = [-1] * n
	taken = [False] * n
	taken[0] = True
	q = deque([0])
	while q:
		v = q.popleft()
		top_sorted.append(v)
		for w in g[v]:
			if not taken[w[0]]:
				taken[w[0]] = True
				q.append(w[0])
				parent[w[0]] = v
	cnt = [0] * n
	for v in top_sorted[::-1]:
		if len(g[v]) == 1:
			cnt[v] = 1
			if parent[v] >= 0:
				cnt[parent[v]] += 1
		elif parent[v] >= 0:
			cnt[parent[v]] += cnt[v]
	ss = 0
	q = []
	for (u, v, w) in e:
		x = cnt[u] if parent[u] == v else cnt[v]
		ss += w * x
		ww = w
		while True:
			delta = x * (ww - ww // 2)
			if delta > 0:
				q.append(delta)
				ww //= 2
			else:
				break
	ans = 0
	q.sort()
	while ss > s:
		ss -= q[-1]
		q.pop()
		ans += 1
	return ans

def main():
	for _ in range(ri()):
		(n, s) = ria()
		g = [[] for i in range(n)]
		e = []
		for i in range(n - 1):
			(u, v, w) = ria()
			u -= 1
			v -= 1
			g[u].append((v, w))
			g[v].append((u, w))
			e.append((u, v, w))
		wi(solve(n, s, g, e))
main()


import sys
from heapq import heappop, heapify
from collections import defaultdict
input = sys.stdin.buffer.readline
t = int(input())
for _ in range(t):
	(n, S) = map(int, input().split())
	adj = [dict() for _ in range(n + 1)]
	for _ in range(n - 1):
		(u, v, w) = map(int, input().split())
		adj[u][v] = w
		adj[v][u] = w
	stack = [1]
	dp = [0] * (n + 1)
	dfs_order = []
	parent = [0] * (n + 1)
	parent[1] = 1
	while stack:
		node = stack.pop()
		dfs_order.append(node)
		leaf = True
		for next_node in adj[node].keys():
			if parent[next_node] == 0:
				parent[next_node] = node
				stack.append(next_node)
				leaf = False
		if leaf:
			dp[node] = 1
	for node in reversed(dfs_order):
		for next_node in adj[node].keys():
			if next_node != parent[node]:
				dp[node] += dp[next_node]
	moves = []
	s = 0
	for (v, c) in enumerate(dp):
		if v == 0 or v == 1:
			continue
		u = parent[v]
		w = adj[u][v]
		s += w * c
		while w > 0:
			moves.append((w // 2 - w) * c)
			w //= 2
	heapify(moves)
	ans = 0
	while s - S > 0:
		s += heappop(moves)
		ans += 1
	print(ans)


from sys import stdin, gettrace
from collections import deque
from heapq import heapify, heappop, heappush
if gettrace():
	inputi = input
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def readGraph(n, m):
	adj = [set() for _ in range(n)]
	for _ in range(m):
		(u, v, w) = map(int, inputi().split())
		adj[u - 1].add((v - 1, w))
		adj[v - 1].add((u - 1, w))
	return adj

def treeOrderByDepth(n, adj, root=0):
	weight = [0] * n
	parent = [-1] * n
	parent[root] = -2
	ordered = []
	q = deque()
	q.append(root)
	while q:
		c = q.popleft()
		ordered.append(c)
		for (a, w) in adj[c]:
			if parent[a] == -1:
				parent[a] = c
				weight[a] = w
				q.append(a)
	return (ordered, parent, weight)

def readTree(n):
	return readGraph(n, n - 1)

def solve():
	(n, s) = map(int, inputi().split())
	adj = readTree(n)
	(ordered, parent, weight) = treeOrderByDepth(n, adj)
	leaves = {i for i in range(1, n) if len(adj[i]) == 1}
	lcount = [1 if i in leaves else 0 for i in range(n)]
	value = [[0, i] for i in range(n)]
	tvalue = 0
	for i in ordered[:0:-1]:
		value[i][0] = -((weight[i] + 1) // 2 * lcount[i])
		tvalue += weight[i] * lcount[i]
		lcount[parent[i]] += lcount[i]
	heapify(value)
	count = 0
	while tvalue > s:
		(v, i) = heappop(value)
		while -v > s or (v <= value[0][0] and tvalue > s):
			tvalue += v
			weight[i] //= 2
			count += 1
			v = -((weight[i] + 1) // 2 * lcount[i])
		heappush(value, [v, i])
	print(count)

def main():
	t = int(inputi())
	for _ in range(t):
		solve()
main()


from collections import deque
import sys
input = sys.stdin.buffer.readline

def print(val):
	sys.stdout.write(str(val) + '\n')

def prog():
	for _ in range(int(input())):
		(n, s) = map(int, input().split())
		adj = [[] for i in range(n)]
		for i in range(n - 1):
			(u, v, w) = map(int, input().split())
			u -= 1
			v -= 1
			adj[u].append([v, w])
			adj[v].append([u, w])
		leaves_in_subtree = [0] * n
		stack = deque([0])
		visited = [0] * n
		parent = [0] * n
		while stack:
			curr = stack[-1]
			if not visited[curr]:
				visited[curr] = 1
				for neighbor in adj[curr]:
					if neighbor[0] != parent[curr]:
						parent[neighbor[0]] = curr
						stack.append(neighbor[0])
			else:
				if len(adj[curr]) == 1:
					leaves_in_subtree[curr] = 1
				else:
					for neighbor in adj[curr]:
						leaves_in_subtree[curr] += leaves_in_subtree[neighbor[0]]
				stack.pop()
		weight_delta = []
		total_weight = 0
		for u in range(1, n):
			for neighbor in adj[u]:
				if neighbor[0] == parent[u]:
					weight = neighbor[1]
					total_weight += weight * leaves_in_subtree[u]
					while weight:
						weight_delta.append((weight - weight // 2) * leaves_in_subtree[u])
						weight //= 2
		weight_delta.sort(reverse=True)
		moves = 0
		idx = 0
		while total_weight > s:
			total_weight -= weight_delta[idx]
			idx += 1
			moves += 1
		print(moves)
prog()


import io
import os
import sys
import threading
import heapq
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_str():
	return input().decode().strip()

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

def oint():
	return int(input())

def dfs(cur):
	stack = [cur]
	while stack:
		cur = stack[-1]
		if v[cur] == 0:
			v[cur] = 1
			for (ni, nw) in adj[cur]:
				if v[ni]:
					continue
				stack.append(ni)
		else:
			if cur != 1 and len(adj[cur]) == 1:
				ret = 1
			else:
				ret = 0
			for (ni, nw) in adj[cur]:
				if v[ni] == 1:
					w[cur] = nw
					continue
				ret += lc[ni]
			lc[cur] = ret
			sl.append((lc[cur] * (w[cur] // 2) - lc[cur] * w[cur], cur))
			v[cur] = 2
			stack.pop()
t = oint()
for _ in range(t):
	(n, s) = rint()
	adj = [[] for i in range(n + 1)]
	v = [0] * (n + 1)
	lc = [0] * (n + 1)
	w = [0] * (n + 1)
	sl = []
	for i in range(n - 1):
		(vv, uu, ww) = rint()
		adj[vv].append((uu, ww))
		adj[uu].append((vv, ww))
	dfs(1)
	sum_ = 0
	for item in sl:
		i = item[1]
		mul = lc[i]
		sum_ += mul * w[i]
	cnt = 0
	heapq.heapify(sl)
	adj = []
	v = []
	while sum_ > s:
		item = heapq.heappop(sl)
		i = item[1]
		mul = lc[i]
		sum_ = sum_ - w[i] * mul + w[i] // 2 * mul
		w[i] //= 2
		if w[i] != 0:
			heapq.heappush(sl, (mul * (w[i] // 2) - mul * w[i], i))
		cnt += 1
	print(cnt)


from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import ceil, floor
from copy import *
from collections import deque, defaultdict
from collections import Counter as counter
from itertools import combinations
from itertools import permutations as permutate
from bisect import bisect_left as bl
from operator import *
from bisect import bisect_right as br
from bisect import bisect
BUFSIZE = 8192
from sys import stderr

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
from types import GeneratorType

def iterative(f, stack=[]):

	def wrapped_func(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		to = f(*args, **kwargs)
		while True:
			if type(to) is GeneratorType:
				stack.append(to)
				to = next(to)
				continue
			stack.pop()
			if not stack:
				break
			to = stack[-1].send(to)
		return to
	return wrapped_func
mod = 1000000007

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def out(var):
	sys.stdout.write(str(var))

def lis():
	return list(map(int, inp().split()))

def stringlis():
	return list(map(str, inp().split()))

def sep():
	return map(int, inp().split())

def strsep():
	return map(str, inp().split())

def fsep():
	return map(float, inp().split())

def nextline():
	out('\n')

def testcase(t):
	for p in range(t):
		solve()

def pow(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
from functools import reduce

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def gcd(a, b):
	if a == b:
		return a
	while b > 0:
		(a, b) = (b, a % b)
	return a

def prefix_sum(ar):
	return list(accumulate(ar))

def suffix_sum(ar):
	return list(accumulate(ar[::-1]))[::-1]

def N():
	return int(inp())
from collections import defaultdict

def numberOfSetBits(i):
	i = i - (i >> 1 & 1431655765)
	i = (i & 858993459) + (i >> 2 & 858993459)
	return ((i + (i >> 4) & 252645135) * 16843009 & 4294967295) >> 24

def solve():
	(n, S) = sep()
	g = [[] for _ in range(n + 1)]
	weigths = defaultdict(int)
	for i in range(n - 1):
		(a, b, w) = sep()
		a -= 1
		b -= 1
		weigths[a, b] = w
		weigths[b, a] = w
		g[a].append(b)
		g[b].append(a)
	dp = [0] * (n + 1)
	temp = []

	@iterative
	def dfs(v, p):
		if len(g[v]) == 1 and g[v][0] == p:
			dp[v] = 1
			temp.append((dp[v], weigths[p, v]))
			yield
		for c in g[v]:
			if c == p:
				continue
			yield dfs(c, v)
			dp[v] += dp[c]
		temp.append((dp[v], weigths[p, v]))
		yield
	tem2 = []
	dfs(0, 0)
	s = 0
	for i in temp:
		(l, w) = i
		s += l * w
		while w > 0:
			tem2.append((w - w // 2) * l)
			w //= 2
	tem2.sort(reverse=True)
	if s <= S:
		print(0)
		return
	for i in range(len(tem2)):
		s -= tem2[i]
		if s <= S:
			print(i + 1)
			return
testcase(int(inp()))


from sys import stdin, stdout
from math import gcd, sqrt
from collections import deque
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())
P = lambda x: stdout.write(x)
lcm = lambda x, y: x * y // gcd(x, y)
hg = lambda x, y: (y + x - 1) // x * x
pw = lambda x: 0 if x == 1 else 1 + pw(x // 2)
chk = lambda x: chk(x // 2) if not x % 2 else True if x == 1 else False
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
for i in range(I()):
	(n, s) = R()
	a = [[] for i in range(n)]
	for i in range(n - 1):
		(x, y, w) = R()
		a[x - 1].append([y - 1, w])
		a[y - 1].append([x - 1, w])
	lf = [0] * n
	p = [0] * n
	v = [1] * n
	stk = [0]
	v[0] = 0
	wt = [0] * n
	srt = [0]
	while stk:
		x = stk.pop()
		flg = True
		for i in a[x]:
			el = i[0]
			ww = i[1]
			if v[el]:
				v[el] = 0
				p[el] = x
				stk += (el,)
				wt[el] = ww
				srt += (el,)
				flg = False
		if flg:
			lf[x] = 1
	cnt = [0] * n
	for i in srt[1:][::-1]:
		if lf[i]:
			cnt[i] += 1
			cnt[p[i]] += 1
		else:
			cnt[p[i]] += cnt[i]
	h = []
	sm = 0
	for i in range(1, n):
		sm += cnt[i] * wt[i]
		w = wt[i]
		while w:
			h += (cnt[i] * (w - w // 2),)
			w //= 2
	h.sort(reverse=True)
	if sm <= s:
		print(0)
	else:
		for i in range(len(h)):
			sm -= h[i]
			if sm <= s:
				print(i + 1)
				break


import sys
input = sys.stdin.buffer.readline

def topological_sort(tree: list, root) -> list:
	n = len(tree)
	visited = [False] * n
	visited[root] = True
	tp_sorted = [root]
	stack = [root]
	while stack:
		v = stack.pop()
		for nxt_v in tree[v]:
			if visited[nxt_v]:
				continue
			visited[nxt_v] = True
			stack.append(nxt_v)
			tp_sorted.append(nxt_v)
	return tp_sorted
t = int(input())
for _ in range(t):
	(n, s) = map(int, input().split())
	edges = [list(map(int, input().split())) for i in range(n - 1)]
	tree = [[] for i in range(n)]
	for (a, b, _) in edges:
		a -= 1
		b -= 1
		tree[a].append(b)
		tree[b].append(a)
	root = 0
	tp_sort = topological_sort(tree, root)
	cnts = [-1] * n
	for v in tp_sort[::-1]:
		cnt = 0
		for nxt_v in tree[v]:
			if cnts[nxt_v] == -1:
				continue
			else:
				cnt += cnts[nxt_v]
		cnts[v] = max(cnt, 1)
	diffs = []
	sum_ = 0
	for (v, chi_v, cost) in edges:
		v -= 1
		chi_v -= 1
		if cnts[v] < cnts[chi_v]:
			(v, chi_v) = (chi_v, v)
		cnt = cnts[chi_v]
		sum_ += cnt * cost
		while True:
			aft_cost = cost >> 1
			diff = cnt * (cost - aft_cost)
			if diff == 0:
				break
			else:
				diffs.append(diff)
				cost = aft_cost
	d = sum_ - s
	diffs.sort(reverse=True)
	ans = 0
	ind = 0
	while d > 0:
		d -= diffs[ind]
		ind += 1
		ans += 1
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

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

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

def N():
	return int(input())

def print_list(l):
	print(' '.join(map(str, l)))
from heapq import *
from collections import defaultdict as dc
for _ in range(N()):
	(n, s) = RL()
	edges = [RLL() for _ in range(n - 1)]
	dic = [[] for _ in range(n + 1)]
	gress = [0] * (n + 1)
	gress[1] = -n - 1
	for (u, v, _) in edges:
		dic[u].append(v)
		dic[v].append(u)
		gress[u] += 1
		gress[v] += 1
	leaf = []
	count = [0] * (n + 1)
	for i in range(2, n + 1):
		if gress[i] == 1:
			leaf.append(i)
			count[i] = 1
	father = [0] * (n + 1)
	now = [1]
	while now:
		node = now.pop()
		for child in dic[node]:
			if child != father[node]:
				father[child] = node
				now.append(child)
	W = [0] * (n + 1)
	for (u, v, w) in edges:
		if father[u] == v:
			W[u] = w
		elif father[v] == u:
			W[v] = w
	weight = []
	now = 0
	while leaf:
		node = leaf.pop()
		f = father[node]
		count[f] += count[node]
		gress[f] -= 1
		if gress[f] == 1:
			leaf.append(f)
		d = W[node] * count[node]
		now += d
		dd = d >> 1
		if W[node] & 1:
			dd += count[node] >> 1
			if count[node] & 1:
				dd += 1
		weight.append((-dd, node))
	heapify(weight)
	res = 0
	while now > s:
		res += 1
		(delta, node) = heappop(weight)
		now += delta
		dd = -delta >> 1
		w = W[node]
		W[node] >>= 1
		if w & 1 == 1 and W[node] & 1 == 0:
			dd -= count[node] >> 1
		elif w & 1 == 0 and W[node] & 1 == 1:
			dd += count[node] >> 1
			if count[node] & 1:
				dd += 1
		heappush(weight, (-dd, node))
	print(res)


from collections import deque
import heapq
t = int(input().split()[0])
for case in range(t):
	(n, s) = map(int, input().split())
	graph = {}
	edgeToWeight = {}
	for i in range(1, n + 1):
		graph[i] = []
	for i in range(n - 1):
		(u, v, w) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
		edgeToWeight[u, v] = w
		edgeToWeight[v, u] = w
	nodeToParent = {}
	visited = [False] * (n + 1)
	queue = deque()
	queue.append(1)
	visited[1] = True
	order = []
	while queue:
		curr = queue.popleft()
		order.append(curr)
		for neighbor in graph[curr]:
			if visited[neighbor] == False:
				nodeToParent[neighbor] = curr
				queue.append(neighbor)
				visited[neighbor] = True
	order.reverse()
	edgeFreq = {}
	for i in range(2, n + 1):
		edgeFreq[i] = 0
	for node in order:
		if node == 1:
			continue
		if len(graph[node]) == 1:
			edgeFreq[node] = 1
		if nodeToParent[node] != 1:
			edgeFreq[nodeToParent[node]] += edgeFreq[node]
	ans = 0
	currSum = 0
	moves = []
	for i in range(2, n + 1):
		wt = edgeToWeight[i, nodeToParent[i]]
		currSum += wt * edgeFreq[i]
		while wt > 0:
			heapq.heappush(moves, (-(wt - wt // 2) * edgeFreq[i], 0))
			wt = wt // 2
	while currSum > s:
		currSum += heapq.heappop(moves)[0]
		ans += 1
	print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import gcd, ceil

def prod(a, mod=10 ** 9 + 7):
	ans = 1
	for each in a:
		ans = ans * each % mod
	return ans

def lcm(a, b):
	return a * b // gcd(a, b)

def binary(x, length=16):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def dfs(graph, alpha):
	n = len(graph)
	visited = [False] * n
	finished = [False] * n
	leaves = [0] * n
	stack = [alpha]
	while stack:
		v = stack[-1]
		if not visited[v]:
			visited[v] = True
			ls = len(stack)
			for u in graph[v]:
				if not visited[u]:
					stack.append(u)
					costs[u] = cost[v, u]
			if len(stack) == ls:
				leaves[v] += 1
		else:
			stack.pop()
			for child in graph[v]:
				if finished[child]:
					leaves[v] += leaves[child]
			finished[v] = True
	return leaves
from heapq import heappop, heappush
for _ in range(int(input()) if True else 1):
	(n, s) = map(int, input().split())
	graph = [[] for __ in range(n + 1)]
	cost = {}
	costs = [0] * (n + 1)
	for i in range(n - 1):
		(x, y, z) = map(int, input().split())
		graph[x] += [y]
		graph[y] += [x]
		cost[x, y] = cost[y, x] = z
	leaves = dfs(graph, 1)
	queue = []
	total = 0
	for u in range(2, n + 1):
		w = costs[u]
		total += leaves[u] * w
		heappush(queue, (-leaves[u] * ceil(w / 2), u))
	ans = 0
	while total > s:
		(k, u) = heappop(queue)
		costs[u] //= 2
		total += k
		ans += 1
		heappush(queue, (-leaves[u] * ceil(costs[u] / 2), u))
	print(ans)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from collections import Counter
from collections import deque
import heapq
import threading
sys.setrecursionlimit(500005)
inp = lambda : int(input())
strng = lambda : input().strip()
jn = lambda x, l: x.join(map(str, l))
strl = lambda : list(input().strip())
mul = lambda : map(int, input().strip().split())
mulf = lambda : map(float, input().strip().split())
seq = lambda : list(map(int, input().strip().split()))
ceil = lambda x: int(x) if x == int(x) else int(x) + 1
ceildiv = lambda x, d: x // d if x % d == 0 else x // d + 1
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
stdarr = lambda : map(int, stdstr().split())
mod = 1000000007

def impac(parent, leaves, ind):
	return (parent[ind] - parent[ind] // 2) * leaves[ind]

def DFS(graph, node, visited, leaves, parent, path, leaf):
	visited[node - 1] = True
	leaves[node - 1] = 0
	for i in graph[node]:
		if visited[i[0] - 1] == False:
			parent[i[0] - 1] = i[1]
			path[i[0]] = path[node] + i[1]
			DFS(graph, i[0], visited, leaves, parent, path, leaf)
			leaves[node - 1] += leaves[i[0] - 1]
	if len(graph[node]) == 1:
		leaves[node - 1] = 1
		leaf.append(node)

def main():
	for _ in range(stdint()):
		(n, s) = stdarr()
		graph = {}
		for i in range(n):
			graph[i + 1] = []
		r = []
		for __ in range(n - 1):
			(a, b, w) = stdarr()
			graph[a].append((b, w))
			graph[b].append((a, w))
		leaves = [0] * n
		visited = [False] * n
		parent = [None] * n
		path = [0] * (n + 1)
		leaf = []
		DFS(graph, 1, visited, leaves, parent, path, leaf)
		impact = []
		for i in range(1, n):
			while parent[i] > 0:
				impact.append(impac(parent, leaves, i))
				parent[i] //= 2
		sn = 0
		for i in leaf:
			sn += path[i]
		moves = 0
		impact = sorted(impact, reverse=True)
		i = 0
		while sn > s:
			sn -= impact[i]
			i += 1
		print(i)
arr = []
max_recur_size = 10 ** 5 * 2 + 1000
max_stack_size = max_recur_size * 500
sys.setrecursionlimit(max_recur_size)
threading.stack_size(max_stack_size)
thread = threading.Thread(target=main)
thread.start()


import math, sys, bisect, heapq, os
from collections import defaultdict, Counter, deque
from itertools import groupby, accumulate
from functools import lru_cache
pr = lambda x: x

def input():
	return sys.stdin.readline().rstrip('\r\n')
aj = lambda : list(map(int, input().split()))

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def Y(c):
	print(['NO', 'YES'][c])

def y(c):
	print(['no', 'yes'][c])

def Yy(c):
	print(['No', 'Yes'][c])

def solve():
	G = defaultdict(list)
	first = 0
	parents = []
	order = []

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

	def DFSutil(node, parents, order):
		my_que = deque()
		my_que.append(node)
		while len(my_que) > 0:
			index = my_que.pop()
			for edge in G.get(index, []):
				if parents[edge] == -2:
					my_que.append(edge)
					parents[edge] = index
					order.append(edge)

	def findsubtree(first, N):
		parents = [-2 for i in range(N)]
		parents[0] = -1
		order = [0]
		size = [0] * N
		for i in range(N):
			if len(G[i]) == 1:
				size[i] = 1
		DFSutil(first, parents, order)
		for z in range(N - 1, 0, -1):
			bb = order[z]
			size[parents[bb]] += size[bb]
		return (size, parents)

	def fun(x):
		(a, b) = x
		return a * b - a // 2 * b

	class Node(object):

		def __init__(self, val: int):
			self.val = val
			(x, y) = val
			self.f = x
			self.s = y

		def __repr__(self):
			return f'Node{self.val}'

		def __lt__(self, other):
			return fun(self.val) > fun(other.val)
	for _ in range(int(input())):
		G = defaultdict(list)
		parents = []
		order = []
		(N, S) = aj()
		E = []
		mark = {}
		for i in range(N - 1):
			(u, v, w) = aj()
			u -= 1
			v -= 1
			addEdge(u, v)
			mark[u, v] = w
			mark[v, u] = w
		(X, par) = findsubtree(first, N)
		H = []
		tot = 0
		for i in range(1, N):
			p = par[i]
			H.append(Node((mark[i, p], X[i])))
			tot += mark[i, p] * X[i]
		if tot <= S:
			print(0)
		else:
			heapq.heapify(H)
			count = 0
			while tot > S:
				x = heapq.heappop(H)
				count += 1
				v = fun((x.f, x.s))
				tot -= v
				newf = x.f // 2
				if newf != 0:
					heapq.heappush(H, Node((newf, x.s)))
			print(count)
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
	from aj import *
except:
	pass
solve()


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
from decimal import Decimal
from fractions import Fraction
INF = float('inf')
mod = int(1000000000.0) + 7
from heapq import heapify, heappush, heappop
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

@bootstrap
def dfs(graph, start, p):
	sum1 = 0
	if len(graph[start]) == 1 and start != 0:
		dp[start] = 1
	for (child, w, c) in graph[start]:
		if child != p:
			sum1 += (yield dfs(graph, child, start))
			sum1 += w * dp[child]
			dp[start] += dp[child]
			if c == 1:
				heappush(q1, ((w // 2 - w) * dp[child], child))
			else:
				heappush(q2, ((w // 2 - w) * dp[child], child))
			v[child] = w
	yield sum1
for t in range(int(data())):
	(n, s1) = mdata()
	g = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v, w, c) = mdata()
		g[u - 1].append((v - 1, w, c))
		g[v - 1].append((u - 1, w, c))
	(q1, q2) = ([], [])
	v = [0] * n
	dp = [0] * n
	sum1 = dfs(g, 0, 0)
	while len(q1) < 2:
		heappush(q1, (0, 0))
	while len(q2) < 1:
		heappush(q2, (0, 0))
	cnt = 0
	while sum1 > s1:
		(dec_a, id_a) = heappop(q1)
		(dec_b, id_b) = q1[0]
		(dec_c, id_c) = q2[0]
		dec = dec_a + min((v[id_a] // 4 - v[id_a] // 2) * dp[id_a], dec_b)
		if sum1 + dec_a <= s1:
			cnt += 1
			break
		if dec_c < dec:
			heappop(q2)
			sum1 += dec_c
			v[id_c] //= 2
			dec_c = (v[id_c] // 2 - v[id_c]) * dp[id_c]
			cnt += 2
			heappush(q2, (dec_c, id_c))
		else:
			sum1 += dec_a
			v[id_a] //= 2
			dec_a = (v[id_a] // 2 - v[id_a]) * dp[id_a]
			cnt += 1
		heappush(q1, (dec_a, id_a))
	out(cnt)


import sys, math
import io, os
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter

def data():
	return sys.stdin.readline().strip()

def mdata():
	return list(map(int, data().split()))

def outl(var):
	sys.stdout.write(' '.join(map(str, var)) + '\n')

def out(var):
	sys.stdout.write(str(var) + '\n')
from decimal import Decimal
from fractions import Fraction
INF = float('inf')
mod = int(1000000000.0) + 7

def dfs(graph, start=0):
	n = len(graph)
	dp = [0] * n
	(visited, finished) = ([False] * n, [False] * n)
	sum1 = 0
	stack = [start]
	while stack:
		start = stack[-1]
		if not visited[start]:
			visited[start] = True
			for (child, w, c) in graph[start]:
				if not visited[child]:
					stack.append(child)
		else:
			stack.pop()
			if len(graph[start]) == 1 and start != 0:
				dp[start] += 1
			for (child, w, c) in graph[start]:
				if finished[child]:
					dp[start] += dp[child]
					sum1 += w * dp[child]
					if c == 1:
						heappush(q1, ((w // 2 - w) * dp[child], child))
					else:
						heappush(q2, ((w // 2 - w) * dp[child], child))
					v[child] = w
			finished[start] = True
	return (dp, sum1)
for t in range(int(data())):
	(n, s1) = mdata()
	g = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v, w, c) = mdata()
		g[u - 1].append((v - 1, w, c))
		g[v - 1].append((u - 1, w, c))
	(q1, q2) = ([], [])
	v = [0] * n
	(dp, sum1) = dfs(g)
	while len(q1) < 2:
		heappush(q1, (0, 0))
	while len(q2) < 1:
		heappush(q2, (0, 0))
	cnt = 0
	while sum1 > s1:
		(dec_a, id_a) = heappop(q1)
		(dec_b, id_b) = q1[0]
		(dec_c, id_c) = q2[0]
		dec = dec_a + min((v[id_a] // 4 - v[id_a] // 2) * dp[id_a], dec_b)
		if sum1 + dec_a <= s1:
			cnt += 1
			break
		if dec_c < dec:
			heappop(q2)
			sum1 += dec_c
			v[id_c] //= 2
			dec_c = (v[id_c] // 2 - v[id_c]) * dp[id_c]
			cnt += 2
			heappush(q2, (dec_c, id_c))
		else:
			sum1 += dec_a
			v[id_a] //= 2
			dec_a = (v[id_a] // 2 - v[id_a]) * dp[id_a]
			cnt += 1
		heappush(q1, (dec_a, id_a))
	out(cnt)


import os
import sys
from io import BytesIO, IOBase
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def dfs(adj, S=1):
	N = len(adj)
	parent = [False] * N
	dp = [0] * N
	edge_value = []

	@bootstrap
	def dfs_run(S):
		ch = 0
		leaves = 0
		for (v, w) in adj[S]:
			if parent[v] == False:
				ch = 1
				parent[v] = True
				lv = (yield dfs_run(v))
				edge_value.append([w, lv])
				leaves += lv
		if ch == 0:
			dp[S] = 1
		else:
			dp[S] = leaves
		yield dp[S]
	parent[S] = True
	dfs_run(S)
	return edge_value
import heapq as hq

def main():
	T = iin()
	while T:
		T -= 1
		(n, S) = lin()
		adj = [[] for i in range(n + 1)]
		for _ in range(n - 1):
			(i, j, w) = lin()
			adj[i].append([j, w])
			adj[j].append([i, w])
		edge_val = dfs(adj)
		Q = 0
		ans = []
		for (w, num) in edge_val:
			x = w
			while x:
				ans.append(x * num - x // 2 * num)
				x //= 2
		ans.sort()
		sm = sum([w * num for (w, num) in edge_val])
		while sm > S and ans:
			val = ans.pop()
			sm -= val
			Q += 1
		print(Q)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def iin():
	return int(input())

def lin():
	return list(map(int, input().split()))
main()


from heapq import heappush, heappop
from collections import deque
mark = [0] * 200002
vw = [0] * 200002
t = int(input())
for test in range(t):
	(n, s) = [int(i) for i in input().split()]
	adj = [[] for j in range(n + 1)]
	deg = [0] * (n + 1)
	v = [0] * (n + 1)
	u = [0] * (n + 1)
	w = [0] * (n + 1)
	for i in range(n - 1):
		(t1, t2, t3) = [int(j) for j in input().split()]
		v[i] = t1
		u[i] = t2
		w[i] = t3
		adj[t1].append(t2)
		adj[t2].append(t1)
		deg[t1] += 1
		deg[t2] += 1
	vw = [0] * (n + 1)
	for i in range(2, n + 1):
		if deg[i] == 1:
			vw[i] = 1
	ei = [0] * (n - 1)
	ew = [0] * (n - 1)
	mark = [0] * (n + 1)
	mark[1] = 1
	q = deque()
	q.append(1)
	qq = []
	p = [0] * (n + 1)
	while len(q) > 0:
		f = q.popleft()
		qq.append(f)
		for i in adj[f]:
			if mark[i] == 0:
				mark[i] = 1
				p[i] = f
				q.append(i)
	for i in range(len(qq) - 1, -1, -1):
		vw[p[qq[i]]] += vw[qq[i]]
	for i in range(n - 1):
		ei[i] = min(vw[v[i]], vw[u[i]])
		ew[i] = w[i]
	pq = []
	sm = 0
	ans = 0
	for i in range(n - 1):
		heappush(pq, (-1 * (ei[i] * ew[i] - ei[i] * (ew[i] // 2)), i))
		sm += ei[i] * ew[i]
	while sm > s:
		ans += 1
		tp = heappop(pq)
		i = tp[1]
		sm += tp[0]
		ew[i] = ew[i] // 2
		heappush(pq, (-1 * (ei[i] * ew[i] - ei[i] * (ew[i] // 2)), i))
	print(ans)


import os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
import heapq
t = int(input())
for _ in range(t):
	(n, s) = map(int, input().split())
	vertexScore = []
	motherEdge = []
	edgeList = []
	inputEdgeList = []
	for _ in range(n):
		edgeList.append([])
		motherEdge.append(-1)
		vertexScore.append(0)
	for _ in range(n - 1):
		(r, m, w) = map(int, input().split())
		inputEdgeList.append((r - 1, m - 1, w))
		edgeList[r - 1].append(m - 1)
		edgeList[m - 1].append(r - 1)
	isAdded = [False] * n
	isAdded[0] = True
	vertexStack = [(0, -1)]
	vertexScoreStack = []
	daughterCountList = [0] * n
	while vertexStack:
		elem = vertexStack.pop()
		motherEdge[elem[0]] = elem[1]
		daughterCount = 0
		for vertex in edgeList[elem[0]]:
			if not isAdded[vertex]:
				isAdded[vertex] = True
				daughterCount += 1
				vertexStack.append((vertex, elem[0]))
		daughterCountList[elem[0]] = daughterCount
		if daughterCount == 0:
			vertexScoreStack.append(elem[0])
	while vertexScoreStack:
		score = 0
		vertex = vertexScoreStack.pop()
		for daughter in edgeList[vertex]:
			if daughter != motherEdge[vertex]:
				score += vertexScore[daughter]
		if score == 0:
			score = 1
		vertexScore[vertex] = score
		if motherEdge[vertex] != -1:
			daughterCountList[motherEdge[vertex]] -= 1
			if daughterCountList[motherEdge[vertex]] == 0:
				vertexScoreStack.append(motherEdge[vertex])
	decrementList = []
	totalScore = 0
	for elem in inputEdgeList:
		if motherEdge[elem[0]] == elem[1]:
			weight = elem[2]
			while weight > 0:
				decScore = weight % 2 + weight // 2
				decScore *= vertexScore[elem[0]]
				decrementList.append(-decScore)
				weight //= 2
			totalScore += vertexScore[elem[0]] * elem[2]
		else:
			weight = elem[2]
			while weight > 0:
				decScore = weight % 2 + weight // 2
				decScore *= vertexScore[elem[1]]
				decrementList.append(-decScore)
				weight //= 2
			totalScore += vertexScore[elem[1]] * elem[2]
	decrementList.sort()
	cnt = 0
	while totalScore > s:
		totalScore += decrementList[cnt]
		cnt += 1
	print(cnt)


import os, sys
from io import BytesIO, IOBase
from collections import defaultdict, Counter
from copy import deepcopy
from heapq import *

class Node:

	def __init__(self, val, occ):
		self.val = val
		self.occ = occ
		self.dec = (val - val // 2) * occ

	def __lt__(self, other):
		return self.dec > other.dec

	def __str__(self):
		return f'{self.val} {self.occ} {self.dec}'

def main():
	for _ in range(int(input())):
		(n, s) = map(int, input().split())
		path = defaultdict(set)
		cost = {}
		for _ in range(n - 1):
			(u, v, w) = map(int, input().split())
			path[u].add(v)
			path[v].add(u)
			cost[u, v] = w
		path1 = deepcopy(path)
		child = Counter()
		st = [1]
		while len(st):
			if not len(path[st[-1]]):
				if not child[st[-1]]:
					child[st[-1]] = 1
				if len(st) > 1:
					child[st[-2]] += child[st[-1]]
				st.pop()
				continue
			i = path[st[-1]].pop()
			path[i].remove(st[-1])
			st.append(i)
		(st, y) = ([1], [])
		while len(st):
			if not len(path1[st[-1]]):
				st.pop()
				continue
			i = path1[st[-1]].pop()
			path1[i].remove(st[-1])
			st.append(i)
			if cost.get((st[-1], st[-2])):
				y.append(Node(cost[st[-1], st[-2]], child[st[-1]]))
				cost[st[-1], st[-2]] *= child[st[-1]]
			else:
				y.append(Node(cost[st[-2], st[-1]], child[st[-1]]))
				cost[st[-2], st[-1]] *= child[st[-1]]
		x = sum(cost.values())
		heapify(y)
		ans = 0
		while x > s:
			z = heappop(y)
			x -= z.dec
			z = Node(z.val // 2, z.occ)
			if z.val:
				heappush(y, z)
			ans += 1
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
import heapq
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, s) = list(map(int, input().split()))
	E = []
	N = [[] for _ in range(n)]
	V = []
	P = [-1 for _ in range(n)]
	E = {}
	for i in range(n - 1):
		(a, b, c) = list(map(int, input().split()))
		a -= 1
		b -= 1
		N[a].append(b)
		N[b].append(a)
		E[a, b] = c
		E[b, a] = c
	visited = [False] * n
	visited[0] = True
	tp_sorted = [0]
	stack = [0]
	NN = [[] for _ in range(n)]
	while stack:
		v = stack.pop()
		for nxt_v in N[v]:
			if visited[nxt_v]:
				continue
			visited[nxt_v] = True
			NN[v].append(nxt_v)
			P[nxt_v] = v
			stack.append(nxt_v)
			tp_sorted.append(nxt_v)
	T = [1 for _ in range(n)]
	tp_sorted = tp_sorted[::-1]
	for v in tp_sorted:
		if len(NN[v]) > 0:
			temp = 0
			for nxt_v in NN[v]:
				temp += T[nxt_v]
			T[v] = temp
	visited = [False] * n
	visited[0] = True
	stack = [0]
	nums = []
	tot = 0
	while stack:
		v = stack.pop()
		for nxt_v in N[v]:
			if visited[nxt_v]:
				continue
			visited[nxt_v] = True
			stack.append(nxt_v)
			temp = E[v, nxt_v] * T[nxt_v]
			jjj = E[v, nxt_v] // 2
			gain = temp - jjj * T[nxt_v]
			tot += temp
			nums.append((-gain, E[v, nxt_v], T[nxt_v]))
	heapq.heapify(nums)
	c = 0
	while tot > s:
		(gain, xx, yy) = heapq.heappop(nums)
		if s == 1:
			tot -= xx * yy
			while xx > 0:
				xx = xx // 2
				c += 1
		else:
			tot += gain
			xx = xx // 2
			gg = xx // 2 * yy - xx * yy
			heapq.heappush(nums, (gg, xx, yy))
			c += 1
	if s == 1 and tot == 0:
		c -= 1
	print(c)


from heapq import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
data = [list(map(int, text.split())) for text in sys.stdin.readlines()]
line = 1
for _ in range(data[0][0]):
	(n, s) = data[line]
	line += 1
	dic = [[] for _ in range(n + 1)]
	(gress, count, father, W, C) = ([0] * (n + 1), [0] * (n + 1), [0] * (n + 1), [0] * (n + 1), [0] * (n + 1))
	gress[1] = -n - 1
	for (u, v, _, _) in data[line:line + n - 1]:
		dic[u].append(v)
		dic[v].append(u)
		gress[u] += 1
		gress[v] += 1
	leaf = []
	now = [1]
	while now:
		node = now.pop()
		if gress[node] == 1:
			count[node] = 1
			leaf.append(node)
		for child in dic[node]:
			if child != father[node]:
				father[child] = node
				now.append(child)
	for (u, v, w, c) in data[line:line + n - 1]:
		if father[u] == v:
			W[u] = w
			C[u] = c
		elif father[v] == u:
			W[v] = w
			C[v] = c
	(weight1, weight2) = ([], [])
	(n1, n2) = (0, 0)
	while leaf:
		node = leaf.pop()
		f = father[node]
		count[f] += count[node]
		gress[f] -= 1
		if gress[f] == 1:
			leaf.append(f)
		delta = ((W[node] >> 1) - W[node]) * count[node]
		if C[node] == 1:
			n1 += W[node] * count[node]
			weight1.append((delta, node))
		else:
			n2 += W[node] * count[node]
			weight2.append((delta, node))
	heapify(weight1)
	heapify(weight2)
	(v1, v2) = ([n1], [n2])
	(t1, t2) = (max(0, s - n2), max(0, s - n1))
	while n1 > t1:
		(delta, node) = heappop(weight1)
		n1 += delta
		v1.append(n1)
		if W[node] > 1:
			W[node] >>= 1
			heappush(weight1, (((W[node] >> 1) - W[node]) * count[node], node))
	while n2 > t2:
		(delta, node) = heappop(weight2)
		n2 += delta
		v2.append(n2)
		if W[node] > 1:
			W[node] >>= 1
			heappush(weight2, (((W[node] >> 1) - W[node]) * count[node], node))
	res = float('inf')
	j = len(v2) - 1
	for i in range(len(v1)):
		if v1[i] > s:
			continue
		while j > 0 and v1[i] + v2[j - 1] <= s:
			j -= 1
		res = min(res, i + 2 * j)
		if i >= res:
			break
	print(res)
	line += n - 1


from collections import *
from sys import stdin, stdout
input = stdin.buffer.readline
print = stdout.write

def ri():
	return int(input())

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

def topo_sort(tree, root, n):
	visited = [False] * (n + 1)
	visited[root] = True
	stack = [root]
	result = [root]
	while stack:
		u = stack.pop()
		for v in tree[u]:
			if visited[v] == False:
				visited[v] = True
				result.append(v)
				stack.append(v)
	return result[::-1]
t = ri()
for _ in range(t):
	(n, S) = rl()
	edges = []
	for i in range(n - 1):
		edges.append(rl())
	tree = defaultdict(list)
	for (u, v, w_, c_) in edges:
		tree[u].append(v)
		tree[v].append(u)
	root = 1
	topo = topo_sort(tree, root, n)
	cnt = [-1] * (n + 1)
	for u in topo:
		this_cnt = 0
		for v in tree[u]:
			if cnt[v] != -1:
				this_cnt += cnt[v]
		cnt[u] = this_cnt
		if cnt[u] == 0:
			cnt[u] = 1
	gains = [[], []]
	sum_weights = 0
	for (child, parent, weight, cost) in edges:
		if cnt[child] > cnt[parent]:
			(child, parent) = (parent, child)
		sum_weights += weight * cnt[child]
		count = cnt[child]
		gain = count * (weight - weight // 2)
		while gain > 0:
			gains[cost - 1].append(gain)
			weight = weight // 2
			gain = count * (weight - weight // 2)
	gains[0].sort(reverse=True)
	gains[1].sort(reverse=True)
	idx1 = 0
	idx2 = 1
	idx22 = 0
	ans = 0
	n1 = len(gains[0])
	n2 = len(gains[1])
	last_idx = -1
	while sum_weights > S:
		if idx1 < n1 and sum_weights - gains[0][idx1] <= S:
			ans += 1
			last_idx = idx1
			break
		if idx2 < n1 and idx22 < n2:
			if gains[0][idx1] + gains[0][idx2] >= gains[1][idx22]:
				ans += 2
				sum_weights -= gains[0][idx1] + gains[0][idx2]
				last_idx = idx2
				idx1 += 2
				idx2 += 2
			else:
				ans += 2
				sum_weights -= gains[1][idx22]
				idx22 += 1
		elif idx22 >= n2:
			ans += 1
			sum_weights -= gains[0][idx1]
			last_idx = idx1
			idx1 += 1
			idx2 += 1
		else:
			ans += 2
			sum_weights -= gains[1][idx22]
			idx22 += 1
	if ans % 2 == 0:
		if last_idx < n1 and last_idx >= 0 and (sum_weights + gains[0][last_idx] <= S):
			ans = max(0, ans - 1)
	print(str(ans) + '\n')