* 第一行: 两个空格分开的数, N和M

* 第2..M+1行: 三个空格分开的数a_i, b_i,和t_i

* 第1..N-1行: 第i行包含一个数:从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最短路经上最后一条牛路的最少的时间.如果这样的路经不存在,输出-1.

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define N 201000#define zff pair
         
          int pos[N],bl[N],point[N],next[N*2],t[N*4],p[N*4],size[N];int f,cnt,num,sz,n,m,x,y,w,fa[N][25],dis[N],deep[N],d[N];bool ff[N];struct use{int st,en,w,f;}e[N*2],b[N*2],c[N*2];using namespace std;priority_queue
          
           
            ,greater
            
              >q;void add(int x,int y,int w){ next[++cnt]=point[x];point[x]=cnt;e[cnt].en=y;e[cnt].w=w;}int Abs(int x){if (x<0) return -x;else return x;}void spfa(){ memset(ff,0,sizeof(f)); memset(d,127,sizeof(d)); d[1]=0;q.push(make_pair(0,1)); while (!q.empty()){ int x=q.top().second;q.pop(); if (ff[x]) continue;ff[x]=1; for (int i=point[x];i;i=next[i]) if (d[e[i].en]>d[x]+e[i].w){ d[e[i].en]=d[x]+e[i].w; q.push(make_pair(d[e[i].en],e[i].en)); } } } void dfs(int x){ size[x]=1; for (int i=1;(1<
             
              <=deep[x];i++) fa[x][i]=fa[fa[x][i-1]][i-1]; for (int i=point[x];i;i=next[i]) if (e[i].en!=fa[x][0]){ deep[e[i].en]=deep[x]+1;dis[e[i].en]=dis[x]+e[i].w; fa[e[i].en][0]=x;dfs(e[i].en);size[x]=size[x]+size[e[i].en]; }} void dfs2(int x,int c){ pos[x]=++sz;bl[x]=c;int k(0); for (int i=point[x];i;i=next[i]) if (e[i].en!=fa[x][0]&&size[e[i].en]>size[k]) k=e[i].en; if (!k) return;dfs2(k,c); for (int i=point[x];i;i=next[i]) if (e[i].en!=fa[x][0]&&e[i].en!=k) dfs2(e[i].en,e[i].en);}int lca(int x,int y){ if (deep[x]
              
               =0;i--) if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; if (x==y) return x;else return fa[x][0]; }void paint(int k,int v){t[k]=min(t[k],v);p[k]=min(p[k],v);}void pushdown(int k,int v){paint(k<<1,v);paint(k<<1|1,v);p[k]=t[0];} void add(int k,int l,int r,int ll,int rr,int v){ int mid=(l+r)>>1; if (p[k]) pushdown(k,p[k]); if (ll<=l&&r<=rr){paint(k,v);return;} if (ll<=mid) add(k<<1,l,mid,ll,rr,v); if (rr>mid) add(k<<1|1,mid+1,r,ll,rr,v); t[k]=min(t[k<<1],t[k<<1|1]); }int ask(int k,int l,int r,int x){ int mid=(l+r)>>1; if (p[k]) pushdown(k,p[k]); if (l==r) return t[k]; if (x<=mid) return ask(k<<1,l,mid,x); else return ask(k<<1|1,mid+1,r,x);}void solveadd(int x,int y,int v){ while(bl[x]!=bl[y]){ add(1,1,sz,pos[bl[x]],pos[x],v); x=fa[bl[x]][0]; } if (x!=y) add(1,1,sz,pos[y]+1,pos[x],v); }void solve(){ for (int i=1;i<=num;i++){ int f=lca(b[i].st,b[i].en); solveadd(b[i].st,f,dis[b[i].en]+b[i].w+dis[b[i].st]); solveadd(b[i].en,f,dis[b[i].en]+b[i].w+dis[b[i].st]); } for (int i=2;i<=n;i++){ int f=ask(1,1,sz,pos[i]); if (f==t[0]) printf("-1\n"); else printf("%d\n",f-dis[i]); }}int main(){ scanf("%d%d",&n,&m);memset(t,127,sizeof(t));memset(p,127,sizeof(p)); for (int i=1;i<=m;i++){ scanf("%d%d%d",&x,&y,&w); c[i].st=x,c[i].en=y,c[i].w=w; add(x,y,w),add(y,x,w); } spfa();memset(point,0,sizeof(point));memset(next,0,sizeof(next));cnt=0; for (int i=1;i<=m;i++)if(Abs(d[c[i].st]-d[c[i].en])==c[i].w) c[i].f=1; for (int i=1;i<=m;i++){ if (!c[i].f) b[++num].st=c[i].st,b[num].en=c[i].en,b[num].w=c[i].w; else add(c[i].st,c[i].en,c[i].w),add(c[i].en,c[i].st,c[i].w); } dfs(1),dfs2(1,1); solve();}