传送门

我们建出最短路树,考虑点$i$的答案,一定是$i$走到子树内的某个点后,通过一条非树边走出$i$的子树,然后再一路走到根。考虑一条非树边,它只会影响两个点到lca之间路径上的点。所以树剖一下,然后随便维护一些最值就做完了。

#include <cstdio>
#include <cstring>
#include <queue>
#define MAXN 200010
#define LL long long
using namespace std;

struct edge{
    int to,next,w;
    edge(int _to=0,int _next=0,int _w=0):to(_to),next(_next),w(_w){}
}e[MAXN<<1];

int n,m,sizew;
int e2[MAXN][3];
int g[MAXN],nume;
int dep[MAXN],pre[MAXN],prei[MAXN],size[MAXN],son[MAXN],top[MAXN],w[MAXN],numw;
LL d[MAXN];
LL a[MAXN<<2];

void addEdge(int u,int v,LL w){
    e[nume]=edge(v,g[u],w);
    g[u]=nume++;
}

void SPFA(){
    static queue<int> Q;
    static bool inque[MAXN];
    memset(d,0x11,sizeof d);
    Q.push(1);
    d[1]=0;
    inque[1]=1;
    while(!Q.empty()){
        int x=Q.front();
        Q.pop();
        inque[x]=0;
        for(int i=g[x];~i;i=e[i].next)
            if(d[x]+e[i].w<d[e[i].to]){
                d[e[i].to]=d[x]+e[i].w;
                pre[e[i].to]=x;
                prei[e[i].to]=i/2+1;
                if(!inque[e[i].to]){
                    inque[e[i].to]=1;
                    Q.push(e[i].to);
                }
            }
    }
}

void dfs(int x){
    size[x]=1;
    son[x]=0;
    for(int i=g[x];~i;i=e[i].next){
        dep[e[i].to]=dep[x]+1;
        dfs(e[i].to);
        size[x]+=size[e[i].to];
        if(size[e[i].to]>size[son[x]]) son[x]=e[i].to;
    }
}

void dfs2(int x){
    w[x]=++numw;
    if(son[x]){
        top[son[x]]=top[x];
        dfs2(son[x]);
    }
    for(int i=g[x];~i;i=e[i].next)
        if(e[i].to^son[x]){
            top[e[i].to]=e[i].to;
            dfs2(e[i].to);
        }
}

int getLCA(int x,int y){
    while(top[x]^top[y]){
        if(dep[top[x]]<dep[top[y]]) x^=y^=x^=y;
        x=pre[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}

void setMax(int x,int cl,int cr,int l,int r,LL v){
    if(l<=cl && cr<=r){
        if(v<a[x]) a[x]=v;
        return;
    }
    int mid=(cl+cr)>>1;
    if(l<=mid) setMax(x<<1,cl,mid,l,r,v);
    if(r>mid) setMax(x<<1|1,mid+1,cr,l,r,v);
}

LL query(int x){
    LL res=a[0];
    for(int i=sizew+x-1;i;i>>=1)
        if(a[i]<res) res=a[i];
    return res;
}

void gao(int x,int y,LL v){
    while(top[x]^top[y]){
        setMax(1,1,sizew,w[top[x]],w[x],v);
        x=pre[top[x]];
    }
    if(x^y) setMax(1,1,sizew,w[y]+1,w[x],v);
}

int main(){
#ifdef DEBUG
    freopen("131.in","r",stdin);
#endif
    memset(a,0x77,sizeof a);
    memset(g,-1,sizeof g);
    scanf("%d%d",&n,&m);
    for(sizew=1;sizew<n;sizew<<=1);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        addEdge(u,v,w);
        addEdge(v,u,w);
        e2[i][0]=u;
        e2[i][1]=v;
        e2[i][2]=w;
    }
    SPFA();
    memset(g,-1,sizeof g);
    nume=0;
    for(int i=2;i<=n;i++) addEdge(pre[i],i,d[i]-d[pre[i]]);
    dfs(1);
    top[1]=1;
    dfs2(1);
    for(int i=1;i<=m;i++){
        int u=e2[i][0],v=e2[i][1];
        if(prei[u]==i || prei[v]==i) continue;
        int lca=getLCA(u,v);
        gao(u,lca,d[v]+d[u]+e2[i][2]);
        gao(v,lca,d[v]+d[u]+e2[i][2]);
    }
    for(int i=2;i<=n;i++){
        LL res=query(w[i])-d[i];
        if(res+d[i]==a[0]) res=-1;
        printf("%lld\n",res);
    }
    return 0;
}