// de facto este Bellman-Ford

#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<cstdio>
#include<string>
using namespace std;
#define foreach(v)   for(typeof (v).begin() it=(v).begin();it!=(v).end();it++)
#define oo 0x3f3f3f3f
struct nod_{
    int nod,lg;
};
vector<nod_> G[50005];
queue<int> q;
int dist[50005];
int isinq[50005];

int m,n;
#define DIM 8192

char ax[DIM];


inline void cit(int &x)
{int pz;
	x=0;
	while(ax[pz]< '0' || ax[pz] > '9')
		if(++pz==DIM)fread(ax,1,DIM,stdin),pz=0;
	while(ax[pz]>='0' && ax[pz]<='9')
	{
		x=x*10+ax[pz]-'0';
		if(++pz==DIM)fread(ax,1,DIM,stdin),pz=0;
	}
}



inline void citire()
{int i,x,y,z;
    freopen("dijkstra.in","r",stdin);
    cit(n);cit(m);

    for(i=1;i<=m;i++)
      {cit(x);cit(y);cit(z);
      G[x].push_back((nod_){y,z});

      }

}


int main()
{int i,u;
    citire();
    freopen("dijkstra.out","w",stdout);
    q.push(1);
    dist[1]=0;
    isinq[1]=1;
    for(i=2;i<=n;i++)
      dist[i]=oo;

    while(!q.empty())
    {
        u=q.front();
        q.pop();
        isinq[u]=0;
        foreach(G[u])
        {

               if(dist[u]+it->lg<dist[(*it).nod])
               {dist[it->nod]=dist[u]+it->lg;


               if(isinq[it->nod]==0)
               {q.push(it->nod);
               isinq[it->nod]=1;
               }
               }
        }
    }

    for(i=2;i<=n;i++)
    if(dist[i]==0x3f3f3f3f)
    printf("%d ", 0);
    else
    printf("%d ",dist[i]);


    return 0;
}