stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<bits/stdc++.h>

#define int long long

using namespace std;

const int N=2*1e5+10,mod=1e9+7;;

int c[N],w[N];

int minn[N];

int numcol[N];

int cnt=0;

int n;

int fac[N],inv[N];

int poww(int x,int y)

{

	int sum=1ll;

	while(y)

	{

		if(y&1)sum=(sum*x)%mod;

		x=(x*x)%mod;

		y>>=1;

	}

	return sum;

}

void prec()

{

	fac[0]=1;

	for(int i=1;i<=n;i++)fac[i]=i*fac[i-1]%mod;

	inv[n]=poww(fac[n],mod-2);

	for(int i=n-1;i>=0;i--)inv[i]=inv[i+1]*(i+1)%mod;

}

int C(int x,int y)

{

	return ((fac[y]*inv[y-x])%mod*inv[x])%mod;

}

signed main()

{

	memset(minn,127,sizeof(minn));

	int x,y;

	scanf("%lld %lld %lld",&n,&x,&y);

	for(int i=1;i<=n;i++)	

	{

		scanf("%lld %lld",&c[i],&w[i]);

		minn[c[i]]=min(minn[c[i]],w[i]);

	}

	int fir_min=0,sec_min=0;

	for(int i=1;i<=n;i++)

	{

		if(minn[i]<minn[fir_min])

		{

			sec_min=fir_min;

			fir_min=i;

		}

		else if(minn[i]<minn[sec_min])sec_min=i;

	}

	for(int i=1;i<=n;i++)

	{

		if(w[i]+minn[c[i]]<=x)w[i]=minn[c[i]];

		if((c[i]==fir_min&&minn[sec_min]+w[i]<=y)||(c[i]!=fir_min&&minn[fir_min]+w[i]<=y))

		{

			numcol[c[i]]++;

			cnt++;

		}

	}

	prec();

	int ans=1;

	for(int i=1;i<=n;i++)

	{

		if(numcol[i])

		{

			ans=(ans*C(numcol[i],cnt))%mod;

			cnt-=numcol[i];

		}

	}

	printf("%lld",ans);

	return 0;

}

/*

4 7 3

3 2

4 3

2 1

4 4

*/

// Faster C++ solution for the same problem (measured speedup: 1.4501960028392316x):
//Created Time:2019年12月17日 星期二 18时41分06秒

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#define N 200005

#define mod 1000000007



using namespace std;



int n, x, y, mn = 999999999, cnt;

int c[N], a[N], ifac[N], fac[N];



struct Ball{

	int col, w;

}b[N];



int read();

int quick_pow(int ,int);



int main(){

	n = read(), x = read(), y = read();

	memset(c, 127, sizeof c); fac[0] = ifac[0] = 1;

	int pos = 1, poss = 1;

	for(int i = 1; i <= n; ++i){

		int col = read(), w = read();

		c[col] = min(c[col], w); b[i] = (Ball){col, w};

		fac[i] = 1ll * fac[i - 1] * i % mod;

	}

	for(int i = 1; i <= n; ++i)

		if(c[i] < c[pos]) poss = pos, pos = i;

		else if(c[i] < c[poss]) poss = i;

	ifac[n] = quick_pow(fac[n], mod - 2);

	for(int i = n - 1; i; --i)

		ifac[i] = 1ll * ifac[i + 1] * (i + 1) % mod;

	for(int i = 1; i <= n; ++i){

		int col = b[i].col, w = b[i].w;

		if((pos != col && (w + c[pos] <= y || (w + c[col] <= x && c[col] + c[pos] <= y))) || (col == pos && (w + c[pos] <= x || (w + c[poss] <= y && c[poss] + c[pos] <= y))))

			++cnt, ++a[col];

	}

	int ans = fac[cnt];

//	cout << cnt << endl;

	for(int i = 1; i <= n; ++i)

		ans = 1ll * ans * ifac[a[i]] % mod;

	cout << ans << endl;

	return 0;

}



int read(){

	int x = 0; char ch = getchar();

	for(; !isdigit(ch); ch = getchar());

	for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ 48);

	return x;

}



int quick_pow(int x, int y){

	int sum = 1;

	for(; y; y >>= 1, x = 1ll * x * x % mod) if(y & 1) sum = 1ll * sum * x % mod;

	return sum;

}
// Slower C++ solution:
#include<cstdio>

#include<algorithm>

#include<vector>

using namespace std;

int gi(){

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 2e5+5;

const int mod = 1e9+7;

int n,X,Y,inv[N],mn[N],mn1=mod,mn2=mod,ans=1,tot;

vector<int>v[N];

int main(){

	n=gi();X=gi();Y=gi();inv[1]=1;

	for (int i=2;i<=n;++i) inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;

	for (int i=2;i<=n;++i) inv[i]=1ll*inv[i]*inv[i-1]%mod;

	for (int i=1,x;i<=n;++i) x=gi(),v[x].push_back(gi());

	for (int i=1;i<=n;++i)

		if (v[i].size()){

			sort(v[i].begin(),v[i].end());

			mn2=min(mn2,mn[i]=v[i][0]);

			if (mn2<mn1) swap(mn1,mn2);

		}else mn[i]=mod;

	for (int i=1;i<=n;++i){

		int mm=mn[i]==mn1?mn2:mn1,sz=v[i].size();

		while (sz>1&&v[i][sz-1]+mn[i]>X&&v[i][sz-1]+mm>Y) --sz,v[i].pop_back();

		if (mn[i]+mn1<=Y) ans=1ll*ans*inv[sz]%mod,tot+=sz;

	}

	for (int i=1;i<=tot;++i) ans=1ll*ans*i%mod;

	printf("%d\n",ans);return 0;

}


// Faster C++ solution for the same problem (measured speedup: 6.465469674607098x):
#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(register int i=(a);i<=(b);++i)

#define dep(i,b,a) for(register int i=(b);i>=(a);--i)

inline char gc(){

	static char buf[100000],*p1=buf,*p2=buf;

	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline int rd(){

	int x=0,fl=1;char ch=gc();

	for(;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;

	for(;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);

	return x*fl;

}

const int N=200002,M=1e9+7;

int n,X,Y,sum,ans,jl[N],mn[N],val[N],fac[N],ny[N],col[N];

int pw(int x,int y){

	int z=1;

	for (;y;y>>=1,x=1ll*x*x%M)

		if (y&1) z=1ll*z*x%M;

	return z;

}

int C(int aa,int bb){return 1ll*fac[bb]*ny[aa]%M*ny[bb-aa]%M;}

int main(){

	n=rd(),X=rd(),Y=rd();

	fac[0]=1;

	rep(i,1,n){

		col[i]=rd(),val[i]=rd();

		jl[col[i]]++;

		mn[i]=1e9;

		fac[i]=(1ll*fac[i-1]*i)%M;

	}

	ny[n]=pw(fac[n],M-2);

	dep(i,n,1) ny[i-1]=(1ll*ny[i]*i)%M;

	rep(i,1,n) mn[col[i]]=min(mn[col[i]],val[i]);

	int mx=0,mxx=0;

	rep(i,1,n)

		if (mn[i]!=1e9)

			if (!mx || mn[i]<mn[mx]) mxx=mx,mx=i;

			else if(!mxx || mn[i]<mn[mxx]) mxx=i;

	rep(i,1,n)

		if (!(mn[col[i]]!=val[i] && mn[col[i]]+val[i]<=X || col[i]==mx && val[i]+mn[mxx]<=Y || col[i]!=mx && val[i]+mn[mx]<=Y)) jl[col[i]]--;

	ans=1,sum=jl[mx];

	rep(i,1,n)

		if (i!=mx && mn[i]+mn[mx]<=Y) sum+=jl[i],ans=1ll*ans*C(jl[i],sum)%M;

	printf("%d",ans);

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<vector>

#define ll long long

#define re register

#define il inline

#define pb push_back

#define fp(i,a,b) for(re int i=a;i<=b;++i)

#define fq(i,a,b) for(re int i=a;i>=b;--i)

using namespace std;

const int N=2e5+100,mod=1e9+7;

int n,x,X,Y,mn[N],mn1=mod,mn2=mod,ans=1,inv[N],tot;

vector<int>V[N];

il ll gi()

{

  re ll x=0,t=1;

  re char ch=getchar();

  while(ch!='-'&&(ch<'0'||ch>'9')) x=x*10+ch-48,ch=getchar();

  if(ch=='-') t=-1,ch=getchar();

  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();

  return x*t;

}

int main()

{

  n=gi();X=gi();Y=gi();

  inv[0]=inv[1]=1;

  fp(i,1,n) x=gi(),V[x].pb(gi());

  fp(i,2,n) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

  fp(i,2,n) inv[i]=1ll*inv[i]*inv[i-1]%mod;

  fp(i,1,n)

    if(V[i].size())

      {

	sort(V[i].begin(),V[i].end());

        mn2=min(mn2,mn[i]=V[i][0]);

	if(mn2<mn1) swap(mn1,mn2);

      }

    else mn[i]=mod;

  fp(i,1,n)

    {

      re int mm=(mn[i]==mn1?mn2:mn1),sz=V[i].size();

      while(sz>1&&V[i][sz-1]+mm>Y&&V[i][sz-1]+mn[i]>X) --sz;

      if(mm+mn[i]<=Y) ans=1ll*ans*inv[sz]%mod,tot+=sz;

    }

  fp(i,1,tot) ans=1ll*ans*i%mod;

  printf("%d\n",ans);

  return 0;

}


// Faster C++ solution for the same problem (measured speedup: 6.549372033237813x):
#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(register int i=(a);i<=(b);++i)

#define dep(i,b,a) for(register int i=(b);i>=(a);--i)

inline char gc(){

	static char buf[100000],*p1=buf,*p2=buf;

	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline int rd(){

	int x=0,fl=1;char ch=gc();

	for(;ch<48||ch>57;ch=gc())if(ch=='-')fl=-1;

	for(;48<=ch&&ch<=57;ch=gc())x=(x<<3)+(x<<1)+(ch^48);

	return x*fl;

}

const int N=200002,M=1e9+7;

int n,X,Y,sum,ans,jl[N],mn[N],val[N],fac[N],ny[N],col[N];

int pw(int x,int y){

	int z=1;

	for (;y;y>>=1,x=1ll*x*x%M)

		if (y&1) z=1ll*z*x%M;

	return z;

}

int C(int aa,int bb){return 1ll*fac[bb]*ny[aa]%M*ny[bb-aa]%M;}

int main(){

	n=rd(),X=rd(),Y=rd();

	fac[0]=1;

	rep(i,1,n){

		col[i]=rd(),val[i]=rd();

		jl[col[i]]++;

		mn[i]=1e9;

		fac[i]=(1ll*fac[i-1]*i)%M;

	}

	ny[n]=pw(fac[n],M-2);

	dep(i,n,1) ny[i-1]=(1ll*ny[i]*i)%M;

	rep(i,1,n) mn[col[i]]=min(mn[col[i]],val[i]);

	int mx=0,mxx=0;

	rep(i,1,n)

		if (mn[i]!=1e9)

			if (!mx || mn[i]<mn[mx]) mxx=mx,mx=i;

			else if(!mxx || mn[i]<mn[mxx]) mxx=i;

	rep(i,1,n)

		if (!(mn[col[i]]!=val[i] && mn[col[i]]+val[i]<=X || col[i]==mx && val[i]+mn[mxx]<=Y || col[i]!=mx && val[i]+mn[mx]<=Y)) jl[col[i]]--;

	ans=1,sum=jl[mx];

	rep(i,1,n)

		if (i!=mx && mn[i]+mn[mx]<=Y) sum+=jl[i],ans=1ll*ans*C(jl[i],sum)%M;

	printf("%d",ans);

}
// Slower C++ solution:
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const long long MAXN=200005,INF=2000000005,MOD=1e9+7;

long long n,X,Y;

long long a[MAXN],w[MAXN],c[MAXN],d[MAXN];

long long jc[MAXN],Inv[MAXN];

long long ksm(long long x,long long y)

{

	long long k=1;

	while(y)

	{

		if(y&1)

			k=(k*x)%MOD;

		x=(x*x)%MOD;

		y>>=1;

	}

	return k;

}

void Init()

{

	jc[0]=1;

	for(long long i=1;i<MAXN;i++)

		jc[i]=(jc[i-1]*i)%MOD;

	Inv[MAXN-1]=ksm(jc[MAXN-1],MOD-2);

	for(long long i=MAXN-2;i>=0;i--)

		Inv[i]=(Inv[i+1]*(i+1))%MOD;

}

int main()

{

	//freopen("colorball.in","r",stdin);

	//freopen("colorball.out","w",stdout);

	Init();

	scanf("%lld %lld %lld",&n,&X,&Y);

	for(long long i=0;i<=n;i++)

		c[i]=INF;

	for(long long i=1;i<=n;i++)

	{

		scanf("%lld %lld",&a[i],&w[i]);

		c[a[i]]=min(c[a[i]],w[i]);

	}

	long long MI=c[1]<c[2]?1:2,MC=c[1]<c[2]?2:1;

	for(long long i=3;i<=n;i++)

	{

		if(c[i]<c[MI])

		{

			MC=MI;

			MI=i;

		}

		else if(c[i]<c[MC])

			MC=i;

	}

	for(long long i=1;i<=n;i++)

		if(w[i]+c[a[i]]<=X)

			w[i]=c[a[i]];

	long long o=0;

	for(long long i=1;i<=n;i++)

		if((w[i]+c[MI]<=Y&&MI!=a[i])||(w[i]+c[MC]<=Y&&MC!=a[i]))

		{

			o++;

			d[a[i]]++;

		}

	long long ans=jc[o];

	for(long long i=1;i<=n;i++)

	{

		if(d[i])

			ans=(ans*Inv[d[i]])%MOD;

	}

	printf("%lld\n",ans);

	fclose(stdin);

	fclose(stdout);

}

// Faster C++ solution for the same problem (measured speedup: 17.542404113316692x):
#include <algorithm>

#include <cstdio>

#include <cstring>



typedef long long LL;



const int MAXN = 200000;

const int MOD = 1000000007;

const int INF = 1000000001;



int N, X, Y, C[MAXN + 5], W[MAXN + 5];



int Min[MAXN + 5], Cnt[MAXN + 5];



int Fac[MAXN + 5], Inv[MAXN + 5];



int Pow(int x, int y) {

	int ret = 1;

	while (y) {

		if (y & 1)

			ret = (LL)ret * x % MOD;

		y >>= 1;

		x = (LL)x * x % MOD;

	}

	return ret;

}



int main() {

	scanf("%d%d%d", &N, &X, &Y);

	Fac[0] = 1;

	for (int i = 1; i <= N; i++)

		Fac[i] = (LL)Fac[i - 1] * i % MOD;

	Inv[N] = Pow(Fac[N], MOD - 2);

	for (int i = N - 1; i >= 0; i--)

		Inv[i] = (LL)Inv[i + 1] * (i + 1) % MOD;

	for (int i = 0; i <= N; i++)

		Min[i] = INF;

	for (int i = 1; i <= N; i++) {

		scanf("%d%d", &C[i], &W[i]);

		Cnt[C[i]]++;

		Min[C[i]] = std::min(Min[C[i]], W[i]);

	}

	int fir = std::min_element(Min + 1, Min + N + 1) - Min, sec = 0;

	for (int i = 1; i <= N; i++)

		if (i != fir && Min[i] < Min[sec])

			sec = i;

	for (int i = 1; i <= N; i++) { // 对于每个球

		if (W[i] != Min[C[i]] && W[i] + Min[C[i]] <= X) // 内部就可以交换

			continue;

		if (C[i] != fir && W[i] + Min[fir] <= Y) // 可交换出去

			continue;

		if (C[i] == fir && W[i] + Min[sec] <= Y) // 可交换出去

			continue;

		Cnt[C[i]]--; // 该球无法移动

	}

	int tot = 0, Ans = 1;

	for (int i = 1; i <= N; i++) // 合并每个颜色的连通块

		if (Min[i] + Min[fir] <= Y)

			Ans = (LL)Ans * Inv[Cnt[i]] % MOD, tot += Cnt[i];

	printf("%d", (LL)Ans * Fac[tot] % MOD);

}
// Slower C++ solution:
#include <iostream>

#include <vector>

using namespace std;



typedef struct P {

	int p, d;

	bool operator<(const P &r) {

		return d < r.d;

	}

} P;

int n, d[10001];

vector<P> v;



int main(){

	int p, d1, d2;

	while (cin >> n && n != 0) {

		v = vector<P>();

		for (int i = 0; i < n; i++) {

			cin >> p >> d1 >> d2;

			v.push_back({ p,d1 + d2 });

		}

		P m = v[0];

		for (int i = 1; i < v.size(); i++) {

			if (m < v[i]) {

				m = v[i];

			}

		}

		cout << m.p << " " << m.d << endl;

	}



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.230175009973045x):
#include <cstdio>

#include <vector>

using namespace std;



typedef struct P {

	int p, d;

	bool operator<(const P &r) {

		return d < r.d;

	}

} P;

int n;;



int main(){

	int p, d1, d2;

	while (true) {

		scanf("%d", &n);

		if (n == 0) break;

		P m = { 0,-1 };

		P t;

		for (int i = 0; i < n; i++) {

			scanf("%d %d %d", &p, &d1, &d2);

			t = { p,d1 + d2 };

			if (m < t) {

				m = t;

			}

		}

		printf("%d %d\n", m.p, m.d);

	}



	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

using namespace std;



typedef struct P {

	int p, d;

	bool operator<(const P &r) {

		return d < r.d;

	}

} P;

int n, d[10001], vm;

P v[10001];



int main(){

	int p, d1, d2;

	while (cin >> n && n != 0) {

		vm = 0;

		for (int i = 0; i < n; i++) {

			cin >> p >> d1 >> d2;

			v[vm++] = { p,d1 + d2 };

		}

		P m = v[0];

		for (int i = 1; i < vm; i++) {

			if (m < v[i]) {

				m = v[i];

			}

		}

		cout << m.p << " " << m.d << endl;

	}



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.2107713155868725x):
#include <cstdio>

#include <vector>

using namespace std;



typedef struct P {

	int p, d;

	bool operator<(const P &r) {

		return d < r.d;

	}

} P;

int n;;



int main(){

	int p, d1, d2;

	while (true) {

		scanf("%d", &n);

		if (n == 0) break;

		P m = { 0,-1 };

		P t;

		for (int i = 0; i < n; i++) {

			scanf("%d %d %d", &p, &d1, &d2);

			t = { p,d1 + d2 };

			if (m < t) {

				m = t;

			}

		}

		printf("%d %d\n", m.p, m.d);

	}



	return 0;

}
// Slower C++ solution:
#include <iostream>

#include <vector>

using namespace std;



typedef struct P {

	int p, d;

	bool operator<(const P &r) {

		return d < r.d;

	}

} P;

int n;;



int main(){

	int p, d1, d2;

	while (cin >> n && n != 0) {

		P m = { 0,-1 };

		P t;

		for (int i = 0; i < n; i++) {

			cin >> p >> d1 >> d2;

			t = { p,d1 + d2 };

			if (m < t) {

				m = t;

			}

		}

		cout << m.p << " " << m.d << endl;

	}



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.17129169989493x):
#include <cstdio>

#include <vector>

using namespace std;



typedef struct P {

	int p, d;

	bool operator<(const P &r) {

		return d < r.d;

	}

} P;

int n;;



int main(){

	int p, d1, d2;

	while (true) {

		scanf("%d", &n);

		if (n == 0) break;

		P m = { 0,-1 };

		P t;

		for (int i = 0; i < n; i++) {

			scanf("%d %d %d", &p, &d1, &d2);

			t = { p,d1 + d2 };

			if (m < t) {

				m = t;

			}

		}

		printf("%d %d\n", m.p, m.d);

	}



	return 0;

}
// Slower C++ solution:
#include <iostream>



int main(){

	int n;

	while(std::cin >> n, n){

		int max_p, max_d = 0;

		for(;n;n--){

			int p, d1, d2;

			std::cin >> p >> d1 >> d2;

			if(d1 + d2 > max_d)

				max_p = p, max_d = d1 + d2;

		}

		std::cout << max_p << " " << max_d << std::endl;

	}

}

// Faster C++ solution for the same problem (measured speedup: 5.168410405372186x):
#include <cstdio>

main(){int n;while(scanf("%d", &n), n){int t, m = 0, p, a, b;for(;n;n--){scanf("%d%d%d",&p,&a,&b);if(a+b>m)t=p,m=a+b;}printf("%d %d\n",t,m);}}
// Slower C++ solution:
#include<bits/stdc++.h>



using namespace std;



#define int long long



const int N=1e5+5;

int n,pset[N],lazy[N],ans[N];

vector<int> child[N];

vector< pair<int, pair<int,int> > > edge;



void joinset(int u, int v, int w){

    if(child[ pset[u] ].size() > child[ pset[v] ].size()) swap(u, v);

    int pau = pset[u];

    lazy[ pset[v] ] += w * (child[ pset[u] ].size());

    for(int cu : child[ pset[u] ]){

        ans[cu] += lazy[ pset[u] ] + w * child[ pset[v] ].size() - lazy[ pset[v] ];

    }

    for(int cu : child[ pset[u] ]) child[ pset[v] ].push_back(cu), pset[cu] = pset[v];

    child[ pau ].clear();

}



signed main(){

    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin>>n;

    for(int i=1;i<n;++i){

        int u,v,w; cin>>u>>v>>w;

        edge.push_back(make_pair(w,make_pair(u,v)));

    }

    sort(edge.begin(), edge.end());



    for(int i=1;i<=n; ++i) pset[i] = i, child[i].push_back(i);



    for(int i = edge.size()-1; i >= 0; --i){

        joinset(edge[i].second.first, edge[i].second.second, edge[i].first);

    }



    for(int i = 1; i <= n; ++i) cout << ans[i] + lazy[ pset[i] ] << "\n";



    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 3.443326609157101x):
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 5;

struct edge{

	int u,v;

	long long w;

	edge(int a,int b,long long c):u(a),v(b),w(c){}

};

long long lazy[N],res[N];

int n,p[N];

vector<vector<int> > sets;

vector<edge> E;

bool cmp(edge &a,edge &b){

	return a.w<b.w;

}

void dsu(int i,int j,long long w){

	for(int k=0;k<sets[i].size();k++){

		res[sets[i][k]]+=lazy[i]-lazy[j]+w*sets[j].size();

		p[sets[i][k]]=j;

	}

	for(int k=0;k<sets[i].size();k++){

		sets[j].push_back(sets[i][k]);

	}

	sets[i].clear();

}

int main(){

	scanf("%d",&n);

	sets.assign(n+1,vector<int>());

	for(int i=1;i<=n;i++){

		p[i]=i;

		sets[i].push_back(i);

	}

	for(int i=1;i<n;i++){

		int u,v;

		long long w;

		cin>>u>>v>>w;

		E.push_back(edge(u,v,w));

	}

	sort(E.begin(),E.end(),cmp);

	reverse(E.begin(),E.end());

	for(int i=0;i<E.size();i++){

		int u=p[E[i].u];

		int v=p[E[i].v];

		int w=E[i].w;

		if(sets[u].size()>sets[v].size()){

			swap(u,v);

		}

		lazy[v]+=w*sets[u].size();

		dsu(u,v,w);

	}

	for(int i=1;i<=n;i++){

		cout<<res[i]+lazy[p[i]]<<"\n";

	}

}
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<string>

using namespace std;



int main()

{

	string op;

	int num;

	priority_queue<int>pq;

	while (cin >> op)

	{

		if (op == "end") break;

		if (op == "insert")

		{

			cin >> num;

			pq.push(num);

		}

		else if (op == "extract")

		{

			cout << pq.top() << endl;

			pq.pop();

		}

	}

}

// Faster C++ solution for the same problem (measured speedup: 5.231724819843057x):
#include<stdio.h>

#include<cstdlib>

#define NI ( 1<<30 )

int a[2000001];

int H;

void swp(int *a,int *b){

int t = *a; *a = *b; *b = t;

}

void maxtree(int x){

int l = x * 2;

int r = 2 * x + 1;

int p;

if( l <= H && a[l] > a[x])p = l;

else p = x;

if( r <= H && a[r] > a[p])p = r;

if(p != x){

    swp(a+x,a+p);

    maxtree(p);

}

}

int extract(){

int maxv;

if(H < 1)return -NI;

maxv = a[1];

a[1] = a[H--];

maxtree(1);

return maxv;

}



void inserts(int i , int key){

  if( key < a[i] )return;

  a[i] = key ;

  while( i > 1 && a[i / 2] < a[i] ){

    swp(&a[i],&a[i/2]);

    i = i / 2;

  }

}



void insertp(int key){

  H++;

   a[H] = -NI;

   inserts(H,key);

}



int main(){

int key;

char s[10];

while(1){

    scanf("%s",s);

    if(s[0] == 'e' && s[1] == 'n')break;

    else if(s[0] == 'i'){

        scanf("%d",&key);insertp(key);

    }

    else printf("%d\n",extract());

}

return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstring>

#include <cstdio>

#include <algorithm>

using namespace  std;

const int N=2e6+5;

#define INFTY (1<<30)

int h,a[N];

void maxheapify(int i){

    int l,r,largest;

    l=2*i;

    r=2*i+1;

    if(l<=h&&a[l]>a[i]) largest=l;

    else largest=i;

    if(r<=h&&a[r]>a[largest]) largest=r;

    if(largest!=i){

        swap(a[i],a[largest]);

        maxheapify(largest);

    }

}

int extract(){

    int maxv;

    if(h<1) return -INFTY;

    maxv=a[1];

    a[1]=a[h--];

    maxheapify(1);

    return maxv;

}

void increasekey(int i,int key){

    if(key<a[i]) return;

    a[i]=key;

    while(i>1&&a[i/2]<a[i]){

        swap(a[i],a[i/2]);

        i/=2;

    }

}

void insert(int key){

    h++;

    a[h]=-INFTY;

    increasekey(h, key);

}

int main(){

    int key;

    char com[10];

    while(1){

        scanf("%s",com);

        if(com[0]=='e'&&com[1]=='n') break;

        if(com[0]=='i'){

            scanf("%d",&key);

            insert(key);

        }

        else

            printf("%d\n",extract());

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.135446245182464x):
#include<stdio.h>

#include<cstdlib>

#define NI ( 1<<30 )

int a[2000001];

int H;

void swp(int *a,int *b){

int t = *a; *a = *b; *b = t;

}

void maxtree(int x){

int l = x * 2;

int r = 2 * x + 1;

int p;

if( l <= H && a[l] > a[x])p = l;

else p = x;

if( r <= H && a[r] > a[p])p = r;

if(p != x){

    swp(a+x,a+p);

    maxtree(p);

}

}

int extract(){

int maxv;

if(H < 1)return -NI;

maxv = a[1];

a[1] = a[H--];

maxtree(1);

return maxv;

}



void inserts(int i , int key){

  if( key < a[i] )return;

  a[i] = key ;

  while( i > 1 && a[i / 2] < a[i] ){

    swp(&a[i],&a[i/2]);

    i = i / 2;

  }

}



void insertp(int key){

  H++;

   a[H] = -NI;

   inserts(H,key);

}



int main(){

int key;

char s[10];

while(1){

    scanf("%s",s);

    if(s[0] == 'e' && s[1] == 'n')break;

    else if(s[0] == 'i'){

        scanf("%d",&key);insertp(key);

    }

    else printf("%d\n",extract());

}

return 0;

}
// Slower C++ solution:
#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <vector>

#include <stack>

#include <queue>

#include <set>

#include <map>

#include <string>

#include <cmath>

#include <cstdlib>

using namespace std;



#define par(x) ((x)>>(1))

#define lc(x) ((x)<<(1))

#define rc(x) ((x)<<(1)|1)



const int MAX = 2000010;

int heap[MAX];

int len;

char cmd[10];



void shiftUp(int p) {

    int parent = par(p);

    if (parent>=1 && heap[parent]<heap[p]) {

        swap(heap[parent], heap[p]);

        shiftUp(parent);

    }

}



void shiftDown(int p) {

    int l = lc(p);

    int r = rc(p);

    int largest = p;

    if (l <= len && heap[l] > heap[p]) {

        largest = l;

    }

    if (r <= len && heap[r] > heap[largest]) {

        largest = r;

    }

    if (largest != p) {

        swap(heap[largest], heap[p]);

        shiftDown(largest);

    }

}



void insert(int x) {

    heap[++len] = x;

    shiftUp(len);

}



int pop() {

    int x = heap[1];

    swap(heap[1], heap[len]);

    len--;

    if (len > 0) {

        shiftDown(1);

    }

    return x;

}



int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    len = 0;

    while (~scanf("%s", cmd)) {

        if (strcmp(cmd, "insert") == 0) {

            int num = 0;

            scanf("%d", &num);

            insert(num);

        } else if (strcmp(cmd, "extract") == 0) {

            printf("%d\n", pop());

        } else if (strcmp(cmd, "end") == 0) {

            break;

        }

    }

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.135802315938849x):
#include<stdio.h>

#include<cstdlib>

#define NI ( 1<<30 )

int a[2000001];

int H;

void swp(int *a,int *b){

int t = *a; *a = *b; *b = t;

}

void maxtree(int x){

int l = x * 2;

int r = 2 * x + 1;

int p;

if( l <= H && a[l] > a[x])p = l;

else p = x;

if( r <= H && a[r] > a[p])p = r;

if(p != x){

    swp(a+x,a+p);

    maxtree(p);

}

}

int extract(){

int maxv;

if(H < 1)return -NI;

maxv = a[1];

a[1] = a[H--];

maxtree(1);

return maxv;

}



void inserts(int i , int key){

  if( key < a[i] )return;

  a[i] = key ;

  while( i > 1 && a[i / 2] < a[i] ){

    swp(&a[i],&a[i/2]);

    i = i / 2;

  }

}



void insertp(int key){

  H++;

   a[H] = -NI;

   inserts(H,key);

}



int main(){

int key;

char s[10];

while(1){

    scanf("%s",s);

    if(s[0] == 'e' && s[1] == 'n')break;

    else if(s[0] == 'i'){

        scanf("%d",&key);insertp(key);

    }

    else printf("%d\n",extract());

}

return 0;

}