#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e6 + 5;
vector<pair<int, int>> adj[MAXN];
ll ans = 0;
int n;

void iterative_dfs() {
    stack<tuple<int, int, bool>> stk;
    stk.emplace(1, -1, false);
    int sub_size[MAXN] = {0};  
    while (!stk.empty()) {
        tuple<int, int, bool> top = stk.top();
        stk.pop();
        int u = get<0>(top);
        int parent = get<1>(top);
        bool is_processed = get<2>(top);
        if (!is_processed) {
            stk.emplace(u, parent, true);
            for (auto it = adj[u].rbegin(); it != adj[u].rend(); ++it) {
                int v = it->first;
                if (v != parent) {
                    stk.emplace(v, u, false);
                }
            }
        } else {
            sub_size[u] = 1;
            for (auto &edge : adj[u]) {
                int v = edge.first;
                int c = edge.second;
                if (v != parent) {
                    sub_size[u] += sub_size[v];
                    ans += (ll)abs(n - 2 * sub_size[v]) * c;
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        adj[a].emplace_back(b, c);
        adj[b].emplace_back(a, c);
    }

    iterative_dfs();
    cout << ans << endl;
    return 0;
}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int a[N],b[N];
void solve() 
{
    priority_queue<int,vector<int>,greater<int>>q;
	int n,m,k;
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		if(k>0)
		{
			k--;
			q.push(a[i]);
		}
		else
		{
			if(q.size()&&q.top()<a[i])
			{
				m-=q.top();
				q.pop();
				q.push(a[i]);
			}
			else
			{
				m-=a[i];
			}
		}
		if(m<=0)
		{
			cout<<i-1<<endl;
			return;
		}
	}
	cout<<n<<endl;
}
signed main() 
{
	//freopen("spire.in","r",stdin);
	//freopen("spire.out","w",stdout);
	cin.tie(0)->sync_with_stdio(0);
	cout.tie(0);
	int T;
	cin>>T;
	while(T--)  
	{
		solve();
	}
	return 0;
}

#include<bits/stdc++.h> using namespace std;

double h,r,ans;

long long s;

int main(){ cin>>h>>r; ans=hrr*3.14159； ans/=1000; ans=20/ans; s=ans; if(s<ans) s+=1; printf("%d",s); return 0; }