#include<cstdio>
#include<vector>
#include<cstring>
#define NMAX 50001
#define INF 0x3f3f3f3f
using namespace std;
typedef struct edge{int y,cost;} muchie;
vector<muchie> G[NMAX];
muchie a;
int val[NMAX],i,j,x,q,now,tail[NMAX],viz[NMAX],n,m;
char buf[32],*p;
int get()
{
	int t;
	for (t=0; *p>='0' && *p<='9';++p)t=t*10 + *p-'0';
	for (;*p==' ';++p);
	return t;
}
int main()
{
	FILE *f = fopen("dijkstra.in","r");
	fgets(buf,sizeof(buf),f);p=buf;
	n = get();
	m = get();
	memset(val,INF,(n+1)*sizeof(int));
	val[1]=0;
	for (i = 1; i <= m; ++i)
	{
		fgets(buf,sizeof(buf),f);p=buf;
		x=get();
		a.y=get();
		a.cost=get();
		G[x].push_back(a);
	}
	for (i = 1;i <= n; i++)
	{
		viz[1]=i;
		tail[0]=tail[1]=1;
		for (j = 1; j <= tail[0]; ++j)
		{
			now = tail[j];
			for (x = 0; x < G[now].size(); ++x)
			{
				q = G[now][x].y;
				if (val[q] > val[now] + G[now][x].cost)
				{
					val[q]=G[now][x].cost + val[now];
				}
				if (viz[q]!=i)
				{
					tail[++tail[0]]=q;
					viz[q]=i;
				}
			}
		}
	}
	FILE *g = fopen("dijkstra.out","w");
	for (i = 2; i <= n; ++i)fprintf(g,"%d ",val[i]);
	fclose(g);


return 0;
}