#include<cstdio>
#include<queue>
#include<vector>
using namespace std;

#define NMAX 50005
#define inf 1999999999
FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");

long n,m,s,d[NMAX],viz[NMAX];


struct cmp{
	bool operator () (long x,long y)
	{ return d[x]>d[y]; }
		  };
		  
struct muchie{
	long x;
	long cost;};


vector <muchie> L[NMAX];
priority_queue <long,vector<long>,cmp> q ;





void dijkstra()
{
long nod;	
	
	s=1;d[s]=0;
	for (long i=2;i<=n;i++)
		d[i]=inf;
	q.push(s);
	viz[s]=1;
	
	while(!q.empty())
		{
    nod=q.top(); viz[nod]=1;
    q.pop();	
	for (long i=0;i<L[nod].size();i++)
		if (d[nod]+L[nod][i].cost < d[ L[nod][i].x ]&&!viz [ L[nod][i].x ])
		  { d[ L[nod][i].x ] = d[nod]+L[nod][i].cost ;
			q.push( L[nod][i].x );
			
		  }
		}
}

int main()
{
	fscanf(f,"%ld%ld",&n,&m);
	
	for (long i=1;i<=m;i++)
	{ long x;
	  muchie y;
	  
	  fscanf(f,"%ld%ld%ld",&x,&y.x,&y.cost);
	  
	  L[x].push_back(y);
	}

	
	dijkstra();
	
	for (long i=2;i<=n;i++)
		if (d[i]==inf)
		fprintf(g,"0 ");
		else
		fprintf(g,"%ld ",d[i]);

	fprintf(g,"\n");	
return 0;}