题目

什么神仙题啊，我怎么只会\(dsu\)啊

我们考虑一个非常暴力的操作，我们利用\(dsu\ on \ tree\)把一棵子树内部的非树边都搞出来，用一个堆来存储

我们从堆顶开始暴力所有的边，如果这条边指向的另外一个点不在当前子树里，我们就把这条边计入答案

这样复杂度显然不是很对，因为我们每次可能要把子树里的边全都访问上一次

考虑让这个暴力的复杂度科学一点

我们发现，如果有一条边在当前这个节点不合法，也就是指向了一个子树内部的边，非常显然，这个点在更往上的点里也会不合法，所以我们直接在这里把这条边给删掉，这样我们就能保证每一条边最多只会被暴力一次了

代码

#include<set>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define fi first
#define se second
#define re register
#define LL long long
#define mp std::make_pair
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read() {
    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
const int inf=999999999;
typedef std::pair<int,int> pii;
const int maxn=1e5+5;
struct E{int v,nxt,w;}e[maxn<<1];
int n,m,num,ans[maxn],Son,__;
int pre[maxn],head[maxn],sum[maxn],son[maxn],dfn[maxn];
std::set<pii> s[maxn];
std::set<pii>::iterator it;
typedef std::pair<int,pii> Pi;
std::priority_queue<Pi,std::vector<Pi>,std::greater<Pi> > q;
inline void Con(int x,int y,int z) {
    e[++num].v=y;e[num].nxt=head[x];
    head[x]=num;e[num].w=z;
}
void dfs1(int x) {
    sum[x]=1;dfn[x]=++__;
    for(re int i=head[x];i;i=e[i].nxt) {
        pre[e[i].v]=pre[x]+e[i].w;
        dfs1(e[i].v);sum[x]+=sum[e[i].v];
        if(sum[e[i].v]>sum[son[x]]) son[x]=e[i].v;
    }
}
namespace Dij {
    std::priority_queue<pii,std::vector<pii>,std::greater<pii> > q;
    struct E{int v,nxt,w;}e[400005];
    int d[maxn],vis[maxn],fa[maxn];
    int num,head[maxn];
    inline void add(int x,int y,int z) {
        e[++num].v=y;e[num].nxt=head[x];
        head[x]=num;e[num].w=z;
    }
    inline void work() {
        for(re int x,y,z,i=1;i<=m;i++) {
            x=read(),y=read(),z=read();
            add(x,y,z),add(y,x,z);
        }
        for(re int i=2;i<=n;i++) d[i]=inf;
        q.push(mp(0,1));
        while(!q.empty()) {
            int k=q.top().second;q.pop();
            if(vis[k]) continue;vis[k]=1;
            for(re int i=head[k];i;i=e[i].nxt)
            if(d[e[i].v]>d[k]+e[i].w) {
                d[e[i].v]=d[k]+e[i].w;fa[e[i].v]=k;pre[e[i].v]=e[i].w;
                q.push(mp(d[e[i].v],e[i].v));
            }
        }
        for(re int i=2;i<=n;i++) Con(fa[i],i,pre[i]);
        dfs1(1);
        for(re int i=1;i<=n;i++)
            for(re int j=head[i];j;j=e[j].nxt) {
                if(fa[i]==e[j].v||fa[e[j].v]==i) continue;
                s[i].insert(mp(e[j].v,pre[e[j].v]+pre[i]+e[j].w));
            }
    }
}
void calc(int x) {
    for(it=s[x].begin();it!=s[x].end();++it) {
        pii now=(*it);
        q.push(mp(now.se,mp(x,now.fi)));
    }
    for(re int i=head[x];i;i=e[i].nxt)
    if(Son!=e[i].v) calc(e[i].v);
}
inline void del(int a,int b,int c) {
    it=s[a].find(mp(b,c));s[a].erase(it);
}
void dfs(int x,int k) {
    for(re int i=head[x];i;i=e[i].nxt)
    if(son[x]!=e[i].v) dfs(e[i].v,0);
    if(son[x]) dfs(son[x],1);
    if(x==1) return;
    Son=son[x],calc(x);Son=0;
    while(!q.empty()) {
        int now=q.top().fi,k=q.top().se.se,t=q.top().se.fi;
        if(dfn[k]>=dfn[x]&&dfn[k]<=sum[x]+dfn[x]-1) {del(t,k,now);q.pop();continue;}
        ans[x]=now-pre[x];break;
    }
    if(!k) while(!q.empty()) q.pop();
}
int main() {
    n=read(),m=read();Dij::work();
    dfs(1,1);
    for(re int i=2;i<=n;i++) 
    if(!ans[i]) puts("-1");else printf("%d\n",ans[i]);
    return 0;
}