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

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

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

 #include<queue>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 const int N=;

 int tr[N<<];

 struct pnt{

     int hd;

     int no;

     int fa;

     int tp;

     int dp;

     int dis;

     int ind;

     int wgt;

     int mxs;

     bool vis;

     bool friend operator < (pnt x,pnt y)

     {

         return x.dis>y.dis;

     }

 }p[N];

 struct ent{

     int twd;

     int lst;

     int vls;

     bool use;

 }e[N<<];

 std::priority_queue<pnt>Q;

 /*class priority_queue{

     public:

         void push(pnt x)

         {

             line[++siz]=x;

             int nw=siz;

             while((nw>>1))

             {

                 int nx=nw>>1;

                 if(line[nx].dis<line[nw].dis)

                     break;

                 std::swap(line[nw],line[nx]);

                 nw=nx;

             }

             return ;

         }

         void pop(void)

         {

             line[1]=line[siz--];

             int nw=1;

             while((nw<<1)<=siz)

             {

                 int nx=nw<<1;

                 if(nx<siz&&line[nx].dis>line[nx+1].dis)

                     nx++;

                 if(line[nw].dis<line[nx].dis)

                     break;

                 std::swap(line[nw],line[nx]);

                 nw=nx;

             }

             return ;

         }

         int top(void)

         {

             return line[1].no;

         }

         bool empty(void)

         {

             return siz==0;

         }

     private:

         pnt line[N];

         int siz;

 }Q;*/

 int n,m;

 int cnt;

 int dfn;

 void ade(int f,int t,int v)

 {

     cnt++;

     e[cnt].twd=t;

     e[cnt].lst=p[f].hd;

     e[cnt].vls=v;

     p[f].hd=cnt;

     return ;

 }

 void Dij(int x)

 {

     for(int i=;i<=n;i++)

     {

         p[i].no=i;

         p[i].dis=0x3f3f3f3f;

     }

     p[].dis=;

     p[].fa=;

     Q.push(p[x]);

     while(!Q.empty())

     {

         x=Q.top().no;

         Q.pop();

         if(p[x].vis)

             continue;

         p[x].vis=true;

         for(int i=p[x].hd;i;i=e[i].lst)

         {

             int to=e[i].twd;

             if(p[to].dis>p[x].dis+e[i].vls)

             {

                 p[to].fa=x;

                 p[to].dis=p[x].dis+e[i].vls;

                 Q.push(p[to]);

             }

         }

     }

     return ;

 }

 void Basic_dfs(int x,int f)

 {

     p[x].dp=p[f].dp+;

     p[x].wgt=;

     int maxs=-;

     for(int i=p[x].hd;i;i=e[i].lst)

     {

         int to=e[i].twd;

         if(p[to].fa!=x||to==f)

         {

             e[i].use=true;

             continue;

         }

         Basic_dfs(to,x);

         p[x].wgt+=p[to].wgt;

         if(maxs<p[to].wgt)

         {

             p[x].mxs=to;

             maxs=p[to].wgt;

         }

     }

     return ;

 }

 void Build_dfs(int x,int top)

 {

     if(!x)

         return ;

     p[x].tp=top;

     p[x].ind=++dfn;

     Build_dfs(p[x].mxs,top);

     for(int i=p[x].hd;i;i=e[i].lst)

     {

         int to=e[i].twd;

         if(p[to].fa!=x||p[to].ind)

             continue;

         Build_dfs(to,to);

     }

     return ;

 }

 int Lca(int x,int y)

 {

     while(p[x].tp!=p[y].tp)

     {

         if(p[p[x].tp].dp<p[p[y].tp].dp)

             std::swap(x,y);

         x=p[p[x].tp].fa;

     }

     if(p[x].dp>p[y].dp)

         std::swap(x,y);

     return x;

 }

 void update(int l,int r,int ll,int rr,int spc,int v)

 {

     if(l>rr||ll>r)

         return ;

     if(ll<=l&&r<=rr)

     {

         tr[spc]=std::min(tr[spc],v);

         return ;

     }

     int mid=(l+r)>>;

     update(l,mid,ll,rr,spc<<,v);

     update(mid+,r,ll,rr,spc<<|,v);

     return ;

 }

 int query(int l,int r,int pos,int spc)

 {

     if(l==r)

         return tr[spc];

     int ans=tr[spc];

     int mid=(l+r)>>;

     if(pos<=mid)

         return std::min(query(l,mid,pos,spc<<),ans);

     else

         return std::min(query(mid+,r,pos,spc<<|),ans);

 }

 int main()

 {

     memset(tr,0x6f,sizeof(tr));

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;i++)

     {

         int a,b,c;

         scanf("%d%d%d",&a,&b,&c);

         ade(a,b,c);

         ade(b,a,c);

     }

     Dij();

     Basic_dfs(,);

     Build_dfs(,);

     for(int i=;i<=cnt;i+=)

     {

         int x,y;

         x=e[i].twd;

         y=e[i+].twd;

         int val=e[i].vls+p[x].dis+p[y].dis;

         int z=Lca(x,y);

         if(e[i].use)

         {

             while(p[x].tp!=p[z].tp)

             {

                 update(,dfn,p[p[x].tp].ind,p[x].ind,,val);

                 x=p[p[x].tp].fa;

             }

             if(x!=z)

                 update(,dfn,p[z].ind+,p[x].ind,,val);

         }

         if(e[i+].use)

         {

             while(p[y].tp!=p[z].tp)

             {

                 update(,dfn,p[p[y].tp].ind,p[y].ind,,val);

                 y=p[p[y].tp].fa;

             }

             if(y!=z)

                 update(,dfn,p[z].ind+,p[y].ind,,val);

         }

     }

     for(int i=;i<=n;i++)

     {

         int ans=0x3f3f3f3f;

         ans=std::min(ans,query(,dfn,p[i].ind,)-p[i].dis);

         if(ans==0x3f3f3f3f)

             ans=-;

         printf("%d\n",ans);

     }

     return ;

 }