求助建虚树

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ll long long
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline void out(int x){
    if(x==0){putchar('0');return;}
    int len=0,k1=x,c[10005];
    if(k1<0)k1=-k1,putchar('-');
    while(k1)c[len++]=k1%10+'0',k1/=10;
    while(len--)putchar(c[len]);
}
const int N=3e5+5,LOGV=20;const ll INF=9e18;
vector<pair<int,int>>g1[N],g2[N];
struct HPD{
    int siz[N],dep[N],tin[N],fa[N],tout[N],h[N],timer=0;ll dist[N];
    void dfs1(int x,int f,vector<pair<int,int>>g[]){
        fa[x]=f,dep[x]=dep[f]+1,tin[x]=++timer,siz[x]=1;h[x]=0;
        for(auto [v,w]:g[x]){
            if(v==f)continue;
            dist[v]=dist[x]+w;
            dfs1(v,x,g);siz[x]+=siz[v];
            if(h[x]==0||siz[h[x]]<siz[v])h[x]=v;
        }tout[x]=timer;
    }int top[N];
    void dfs2(int x,vector<pair<int,int>>g[]){
        if(top[x]==0)top[x]=x; 
        if(h[x]){
            top[h[x]]=top[x];
            dfs2(h[x],g);
        }for(auto [v,w]:g[x]){
            if(v==fa[x]||v==h[x])continue;
            top[v]=v;dfs2(v,g);
        }
    }int lca(int a,int b){
        while(top[a]!=top[b]){
            if(dep[top[a]]<dep[top[b]])swap(a,b);
            a=fa[top[a]];
        }if(dep[a]<dep[b])return a;
        return b;
    }ll dis(int u,int v){return dist[u]+dist[v]-2*dist[lca(u,v)];}
}hpd1,hpd2;
ll ans[N];int sz[N],kid[N];bool flag[N];
void getsz(int x,int fa){
    sz[x]=1;for(auto [v,w]:g1[x]){
        if(v==fa||flag[v])continue;
        getsz(v,x);sz[x]+=sz[v];
    }
}int getcent(int x,int fa,int tot){
    for(auto [v,w]:g1[x]){
        if(v==fa||flag[v])continue;
        if(sz[v]*2>tot)return getcent(v,x,tot);
    }return x;
}vector<int>node;
void get_kid(int x,int fa,int k){
    node.push_back(x);kid[x]=k;
    for(auto [v,w]:g1[x]){
        if(v==fa||flag[v])continue;
        get_kid(v,x,k);
    }return ;
}int idxn[N],idxv[N],curv=1;
void markidx(int x,int idx){idxn[x]=idx;idxv[x]=curv;}
int getidx(int x){if(idxv[x]==curv)return idxn[x];return -1;}
vector<int>tmp;vector<vector<pair<int,ll>>>vg;int up2[LOGV][N];
int lca2(int a,int b){
    if(a==0)return b;if(b==0)return a;
    if(hpd2.tin[a]<=hpd2.tin[b]&&hpd2.tout[a]>=hpd2.tin[b])return a;
    if(hpd2.tin[b]<=hpd2.tin[a]&&hpd2.tout[b]>=hpd2.tin[a])return b;
    for(int k=LOGV-1;k>=0;k--){
        int pa=up2[k][a];
        if(pa==0)continue; 
        if(!(hpd2.tin[pa]<=hpd2.tin[b]&&hpd2.tout[pa]>=hpd2.tin[b]))a=pa;
    }return up2[0][a];
}void build(vector<int>&tree){
    curv++;tmp=tree;tmp.reserve(tree.size()*2);
    sort(tmp.begin(),tmp.end(),[](int u,int v){
        if(hpd2.tin[u]==hpd2.tin[v])return u<v;
        return hpd2.tin[u]<hpd2.tin[v];
    });int m=tmp.size();
    for(int i=0;i<m-1;i++)tmp.push_back(lca2(tmp[i],tmp[i+1]));
    sort(tmp.begin(),tmp.end(),[](int u,int v){
        if(hpd2.tin[u]==hpd2.tin[v])return u<v;
        return hpd2.tin[u]<hpd2.tin[v];
    });tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
    m=tmp.size();vg.assign(m,vector<pair<int,ll>>());
    for(int i=0;i<m;i++)markidx(tmp[i],i);vector<int>st;st.reserve(m);
    for(auto x:tmp){
        while(!st.empty()&&hpd2.tout[st.back()]<hpd2.tin[x])st.pop_back();
        if(!st.empty()){
            int u=st.back(),iu=getidx(u),iv=getidx(x);ll w=hpd2.dis(u,x);
            vg[iu].push_back({iv,w});
            vg[iv].push_back({iu,w});
        }st.push_back(x);
    }
}vector<ll>dist1,dist2;vector<int>src1,src2;
struct state{
    ll d;int vidx,src;
    bool operator<(const state &o)const{return d>o.d;}
};void dij(int c){
    node.clear();node.push_back(c);kid[c]=0;
    for(auto [v,w]:g1[c]){
        if(flag[v])continue;
        get_kid(v,c,v);
    }if(node.size()<=1)return ;build(node);int m=tmp.size();    
    dist1.assign(m,INF);dist2.assign(m,INF);   
    src1.assign(m,-1);src2.assign(m,-1);priority_queue<state>q;
    for(auto s:node){
        int idx=getidx(s);
        if(idx==-1)continue;
        ll w=hpd1.dis(s,c);
        if(src1[idx]==-1){
            dist1[idx]=w,src1[idx]=s;
            q.push({w,idx,s});
        }else if(src1[idx]==s){
            if(w<dist1[idx]){dist1[idx]=w;q.push({w,idx,s});}
        }else{
            if(w<dist1[idx]){
                dist2[idx]=dist1[idx],src2[idx]=src1[idx];
                dist1[idx]=w,src1[idx]=s;
                q.push({w,idx,s});
            }else if(w<dist2[idx]){
                dist2[idx]=w,src2[idx]=s;
                q.push({w,idx,s});
            }
        }
    }while(!q.empty()){
        auto [d,u,src]=q.top();q.pop();
        if(!((src1[u]==src&&dist1[u]==d)||(src2[u]==src&&dist2[u]==d)))continue;
        for(auto [v,w]:vg[u]){
            if(src1[v]==-1){
                dist1[v]=d+w,src1[v]=src;
                q.push({d+w,v,src});
            }else if(src1[v]==src){
                if(d+w<dist1[v])dist1[v]=d+w,q.push({d+w,v,src});
            }else{
                if(d+w<dist1[v]){
                    dist2[v]=dist1[v],src2[v]=src1[v];
                    dist1[v]=d+w,src1[v]=src;
                    q.push({d+w,v,src});
                }else if(d+w<dist2[v]){
                    dist2[v]=d+w,src2[v]=src;
                    q.push({d+w,v,src});
                }
            }
        }
    }for(auto v:node){
        int vidx=getidx(v);if(vidx==-1)continue;
        int s1=src1[vidx],s2=src2[vidx],k=kid[v];
        ll v1=dist1[vidx],v2=dist2[vidx],maxn=INF;
        auto check=[&](int s)->bool {
            if(s==-1||s==c)return 0;
            return kid[s]==k;
        };if(s1!=-1&&s1!=v&&!check(s1))maxn=v1;
        else if(s2!=-1&&s2!=v&&!check(s2))maxn=v2;
        if(maxn<INF){
            ll tmp=hpd1.dis(v,c)+maxn;
            if(tmp<ans[v])ans[v]=tmp;
        }
    }
}void solve(int x){
    getsz(x,0);int c=getcent(x,0,sz[x]);
    dij(c);flag[c]=1;
    for(auto [v,w]:g1[c]){
        if(!flag[v])solve(v);
    }return ;
}
signed main(){
    // freopen("P14622_12.in","r",stdin);
    // freopen("tmp.out","w",stdout);
    int n=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        g1[u].push_back({v,w});
        g1[v].push_back({u,w});
    }for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        g2[u].push_back({v,w});
        g2[v].push_back({u,w});
    }
    hpd1.dfs1(1,0,g1);hpd1.dfs2(1,g1);
    hpd2.dfs1(1,0,g2);hpd2.dfs2(1,g2);
    for(int v=1;v<=n;v++)up2[0][v]=hpd2.fa[v]; 
    for(int k=1;k<LOGV;k++){
        for(int v=1;v<=n;v++){
            int mid=up2[k-1][v];
            up2[k][v]=(mid==0)?0:up2[k-1][mid];
        }
    }for(int i=1;i<=n;i++)ans[i]=INF;solve(1);
    for(int i=1;i<=n;i++){
        if(ans[i]>=INF/2)puts("0");
        else cout<<ans[i]<<"\n";
    }return 0;
}

#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define ll long long
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline void out(int x){
    if(x==0){putchar('0');return;}
    int len=0,k1=x,c[10005];
    if(k1<0)k1=-k1,putchar('-');
    while(k1)c[len++]=k1%10+'0',k1/=10;
    while(len--)putchar(c[len]);
}
const int N=3e5+5;const ll INF=9e18+9;
vector<pair<int,int>>g1[N],g2[N];
struct HPD{
    int siz[N],dep[N],tin[N],fa[N],tout[N],timer=0;ll dist[N];
    void dfs1(int x,int f,vector<pair<int,int>>g[]){
        siz[x]=1,fa[x]=f,dep[x]=dep[f]+1;tin[x]=++timer;
        for(auto [v,w]:g[x]){
            if(v==f)continue;dist[v]=dist[x]+w;
            dfs1(v,x,g);siz[x]+=siz[v];
            if(siz[h[x]]<siz[v])h[x]=v;
        }tout[x]=timer;
    }int top[N],h[N];
    void dfs2(int x,vector<pair<int,int>>g[]){
        top[h[x]]=top[x];
        if(h[x])dfs2(h[x],g);
        for(auto [v,w]:g[x]){
            if(v==fa[x]||v==h[x])continue;
            top[v]=v;dfs2(v,g);
        }
    }int lca(int a,int b){
        while(top[a]!=top[b]){
            if(dep[top[a]]<dep[top[b]])swap(a,b);
            a=fa[top[a]]; 
        }if(dep[a]<dep[b])return a;
        else return b;
    }ll dis(int u,int v){return dist[u]+dist[v]-2*dist[lca(u,v)];}
}hpd1,hpd2;
ll ans[N];int sz[N],kid[N];bool flag[N];
void getsz(int x,int fa){
    sz[x]=1;for(auto [v,w]:g1[x]){
        if(v==fa)continue;
        getsz(v,x);sz[x]+=sz[v];
    }
}int getcent(int x,int fa,int tot){
    for(auto [v,w]:g1[x]){
        if(v==fa||flag[v])continue;
        if(sz[v]*2>tot)return getcent(v,x,tot);
    }return x;
}vector<int>node;
void get_kid(int x,int fa,int k){
    node.push_back(x);kid[x]=k;
    for(auto [v,w]:g1[x]){
        if(v==fa||flag[v])continue;
        get_kid(v,x,k);
    }return ;
}int idxn[N],idxv[N],curv=1;
void markidx(int x,int idx){idxn[x]=idx;idxv[x]=curv;}
int getidx(int x){if(idxv[x]==curv)return idxn[x];return -1;}
vector<int>tmp;vector<vector<pair<int,ll>>>vg;
void build(vector<int>tree){
    curv++;tmp=tree;
    sort(tmp.begin(),tmp.end(),[](int u,int v){
        if(hpd2.tin[u]==hpd2.tin[v])return u<v;
        return hpd2.tin[u]<hpd2.tin[v];
    });int m=tmp.size();
    for(int i=0;i<m-1;i++)tmp.push_back(hpd2.lca(tmp[i],tmp[i+1]));
    sort(tmp.begin(),tmp.end(),[](int u,int v){
        if(hpd2.tin[u]==hpd2.tin[v])return u<v;
        return hpd2.tin[u]<hpd2.tin[v];
    });m=tmp.size();vg.assign(m,vector<pair<int,ll>>());
    for(int i=0;i<m;i++)markidx(tmp[i],i);vector<int>st;st.reserve(m);
    for(auto x:tmp){
        while(!st.empty()&&hpd2.tout[st.back()]<hpd2.tin[x])st.pop_back();
        if(!st.empty()){
            int u=st.back(),iu=getidx(u),iv=getidx(x);ll w=hpd2.dis(u,x);
            vg[iu].push_back({iv,w});
            vg[iv].push_back({iu,w});
        }st.push_back(x);
    }
}vector<ll>dist1,dist2;vector<int>src1,src2;
struct state{
    ll d;int vidx,src;
    bool operator<(const state &o)const{return d>o.d;}
};
void dij(int c){
    node.clear();node.push_back(c);kid[c]=0;
    for(auto [v,w]:g1[c]){
        if(flag[v])continue;
        get_kid(v,c,v);
    }if(node.size()<=1)return ;build(node);int m=tmp.size();    
    dist1.assign(m,INF);dist2.assign(m,INF);
    src1.assign(m,-1);src2.assign(m,-1);priority_queue<state>q;
    for(auto s:node){
        int idx=getidx(s);
        if(idx==-1)continue;
        ll w=hpd1.dis(s,c);
        if(src1[idx]==-1){
            dist1[idx]=w,src1[idx]=s;
            q.push({w,idx,s});
        }else if(src1[idx]==s){
            if(w<dist1[idx]){dist1[idx]=w;q.push({w,idx,s});}
        }else{
            if(w<dist1[idx]){
                dist2[idx]=dist1[idx],src2[idx]=src1[idx];
                dist1[idx]=w,src1[idx]=s;
                q.push({w,idx,s});
            }else if(w<dist2[idx]){
                dist2[idx]=w,src2[idx]=s;
                q.push({w,idx,s});
            }
        }
    }while(!q.empty()){
        auto [d,u,src]=q.top();q.pop();
        if(!((src1[u]==src&&dist1[u]==d)||(src2[u]==src&&dist2[u]==d)))continue;
        for(auto [v,w]:vg[u]){
            if(src1[v]==-1){
                dist1[v]=d+w,src1[v]=src;
                q.push({d+w,v,src});
            }else if(src1[v]==src){
                if(d+w<dist1[v])dist1[v]=d+w,q.push({d+w,v,src});
            }else{
                if(d+w<dist1[v]){
                    dist2[v]=dist1[v],src2[v]=src1[v];
                    dist1[v]=d+w,src1[v]=src;
                    q.push({d+w,v,src});
                }else if(d+w<dist2[v]){
                    dist2[v]=d+w,src2[v]=src;
                    q.push({d+w,v,src});
                }
            }
        }
    }for(auto v:node){
        int vidx=getidx(v);if(vidx==-1)continue;
        int s1=src1[vidx],s2=src2[vidx],k=kid[v];
        ll v1=dist1[vidx],v2=dist2[vidx],maxn=INF;
        auto check=[&](int s)->bool {
            if(s==-1||s==c)return 0;
            return kid[s]==k;
        };if(s1!=-1&&s1!=v&&!check(s1))maxn=v1;
        else if(s2!=-1&&s2!=v&&!check(s2))maxn=v2;
        if(maxn<INF){
            ll tmp=hpd1.dis(v,c)+maxn;
            if(tmp<ans[v])ans[v]=tmp;
        }
    }
}
void solve(int x){
    getsz(x,0);int c=getcent(x,0,sz[x]);
    dij(c);flag[c]=1;
    for(auto [v,w]:g1[c]){
        if(!flag[v])solve(v);
    }return ;
}
signed main(){
    int n=read();
    for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        g1[u].push_back({v,w});
        g1[v].push_back({u,w});
    }for(int i=1;i<n;i++){
        int u=read(),v=read(),w=read();
        g2[u].push_back({v,w});
        g2[v].push_back({u,w});
    }hpd1.dfs1(1,0,g1);hpd1.dfs2(1,g1);
    hpd2.dfs1(1,0,g2);hpd2.dfs2(1,g2);
    for(int i=1;i<=n;i++)ans[i]=INF;solve(1);
    for(int i=1;i<=n;i++){
        if(ans[i]>=INF/2)puts("0");
        else cout<<ans[i]<<"\n";
    }return 0;
}