#include<bits/stdc++.h> #define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0) #define int long long using namespace std; const int mod=1e9+9,inf=0x3f3f3f3f,N=3e5+5; int par[N],sz[N],p2[N],p2i[N],v1[N],v2[N],A,B,C,T,n; vector<pair<int,pair<int,int>>> e; int inv(int a,int m){ int x=a,y=m,u=1,v=0; for(int q;y^1;)q=x/y,x-=q*y,swap(x,y),u-=q*v,swap(u,v); return (v+m)%m; } int ip2(int x){return x>N-5?0:p2i[x];} int fd(int x){return par[x]=par[x]^x?fd(par[x]):x;} signed main(void){ exoworldgd; cin>>n; for(int i=1,a,b,c;i<=n;i++)cin>>a>>b>>c,e.push_back({c,{a,b}}); sort(e.begin(),e.end()),reverse(e.begin(),e.end()),p2[0]=1,fill(sz,sz+N,1),iota(par,par+N,0),sz[0]=inf; for(int i=1;i<=n+1;i++)p2[i]=p2[i-1]*2%mod; for(int i=0;i<=n+1;i++)p2i[i]=inv(p2[i],mod); for(auto x:e){ int w=x.first,a=fd(x.second.first),b=fd(x.second.second),t=ip2(sz[a])+ip2(sz[b])-ip2(sz[a]+sz[b]); t%=mod;if(t<0)t+=mod,B=(B+w*((T-v1[a]-v1[b]+mod)%mod*t%mod))%mod,B=(B+w*(((ip2(sz[b])-ip2(sz[a]+sz[b])+mod)%mod*v2[b]+ip2(sz[a])*v1[b])%mod))%mod,B=(B+w*(((ip2(sz[a])-ip2(sz[b]+sz[a])+mod)%mod*v2[a]+ip2(sz[b])*v1[a])%mod))%mod,A=(A+w*t)%mod,C=(C+w*w%mod*t)%mod,T=(T-v1[a]-v1[b]+2*mod)%mod,par[a]=b,sz[b]+=sz[a],v1[b]=(v1[b]+v1[a]+w*t)%mod,T=(T+v1[b])%mod,v2[b]=(v2[b]+v2[a]+w)%mod; } A=A*p2[n]%mod,B=B*p2[n]%mod,C=(C*p2[n]%mod+B*2)%mod,cout<<A<<"\n"<<C; }