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

FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");

#define INF 999999
#define maxn 50005
#define maxm 250005
vector <int> G[maxm],C[maxn],d(maxn,INF);
queue <pair <int,int> > Q;

int n,m,x,y,c;
void dij(){
	d[1]=0;
	Q.push(make_pair(0,1));
	while(Q.empty()==0){
		int val=Q.front().first;
		int y=Q.front().second; 
		Q.pop();
		for(int i=0;i<G[y].size();i++){
			//int v=G[x][i];
			if(d[G[y][i]]>val+C[y][i]){
				d[G[y][i]]=val+C[y][i];
				Q.push(make_pair(d[G[y][i]],G[y][i]));
			}
		}
	}
}
int main (){
	fscanf(f,"%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		fscanf(f,"%d%d%d",&x,&y,&c);
		G[x].push_back(y);
		//G[y].push_back(x);
		C[x].push_back(c);
	}
	dij();
	for(int i=2;i<=n;i++)
		fprintf(g,"%d ",d[i]);
	return 0;
}