#include<stdio.h>
#include<vector>
#include<utility>
#include<queue>
using namespace std;

#define x first
#define y second

FILE *in,*out;

int m,n;
vector<pair<int,int> > mat[50001];
priority_queue<pair<int,int> , vector<pair<int,int> > , greater<pair<int,int> > > q;
int dist[50001];
int nod1,nod2,dis;
int main(void)
{
	in=fopen("dijkstra.in","rt");
	out=fopen("dijkstra","wt");
	fscanf(in,"%d%d",&n,&m);
	dist[1]=0;
	for(int i=2;i<=n;++i)
		dist[i]=(1<<30)-1;
	
	q.push(make_pair(0,1));
	for(int i=1;i<=m;++i)
	{
		fscanf(in,"%d%d%d",&nod1,&nod2,&dis);
		mat[nod1].push_back(make_pair(dis,nod2));
	}	
	while(!q.empty())
	{
		pair<int,int> curent=q.top();
		q.pop();
		for(int i=0;i<(int)mat[curent.y].size();++i)
		{
			if(mat[curent.y][i].x+curent.x<dist[mat[curent.y][i].y])
			{	
				dist[mat[curent.y][i].y]=mat[curent.y][i].x+curent.x;
				q.push(make_pair(mat[curent.y][i].x+curent.x,mat[curent.y][i].y));
			}	
			
		}	
	}	
	for(int i=2;i<=n;++i)
		if(dist[i]==(1<<30)-1)
			fprintf(out,"0 ");
		else
		fprintf(out,"%d ",dist[i]);
	fclose(in);
	fclose(out);
	return 0;
}