分析：

Dijkstra求最短路树，在最短路树上进行操作，详情可见上一篇博客：

我觉得这个东西不压行写出了有点丑...之后写了一个压行后更丑的...

附上压行后的代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 200005#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define inf 0x3f3f3f3fstruct node{ int to,next,val;}E[N<<2],e[N<<1];int head[N],head1[N],cnt,cnt1,fa[N],a[N];int dep[N],anc[N],siz[N],son[N],idx[N],b[N];int dis[N],minn[N<<2],cov[N<<2],n,vis[N],c[N];void add1(int x,int y,int z){E[cnt1].to=y;E[cnt1].next=head1[x];E[cnt1].val=z;head1[x]=cnt1++;}void add(int x,int y,int z){e[cnt].to=y;e[cnt].next=head[x];e[cnt].val=z;head[x]=cnt++;}void Dijkstra(){ memset(dis,0x3f,sizeof(dis));int num=0; priority_queue
            
             
               >q;dis[1]=0;q.push(make_pair(0,1)); while(!q.empty()) { if(num==n)break; int x=q.top().second;q.pop(); if(vis[x])continue;vis[x]=1;num++; for(int i=head1[x];i!=-1;i=E[i].next) { int to1=E[i].to; if(dis[to1]+E[i].val==dis[x])add(to1,x,E[i].val),add(x,to1,E[i].val); } for(int i=head1[x];i!=-1;i=E[i].next) { int to1=E[i].to; if(dis[x]+E[i].val
              
               >1; build(lson);build(rson);}void Update(int L,int R,int c,int l,int r,int rt){ if(L<=l&&r<=R) { minn[rt]=min(minn[rt],c);cov[rt]=min(cov[rt],c); return ; } PushDown(rt);int m=(l+r)>>1; if(L<=m)Update(L,R,c,lson); if(m
               
                >1; if(m>=x)return query(x,lson); else return query(x,rson);}void get_lca(int x,int y,int c){ while(anc[x]!=anc[y]) { if(dep[anc[x]]
                
                 dep[y])swap(x,y); if(x!=y)Update(idx[x]+1,idx[y],c,1,n,1);}int main(){ int m;memset(head,-1,sizeof(head));memset(head1,-1,sizeof(head1));scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y,z;scanf("%d%d%d",&x,&y,&z); add1(x,y,z);add1(y,x,z);a[i]=x,b[i]=y,c[i]=z; } Dijkstra();dfs1(1,0);dfs2(1,1);build(1,n,1); for(int i=1;i<=m;i++) { if(abs(dis[a[i]]-dis[b[i]])==c[i])continue; get_lca(a[i],b[i],dis[a[i]]+dis[b[i]]+c[i]); } for(int i=2;i<=n;i++) { int t=query(idx[i],1,n,1); t==inf?printf("-1\n"):printf("%d\n",t-dis[i]); } return 0;}