#include<cstdio>
#include<vector>
#include<cstring>
#include<queue>
#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,n,m;
bool viz[NMAX];
queue<int> tail;
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);
	}
	tail.push(1);
	memset(viz,false,sizeof(viz));
	viz[1]=true;
	while (!tail.empty())
	{
		now = tail.front();
		tail.pop();
		viz[now]=false;
		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]==false)
				{
					tail.push(q);
					viz[q]=true;
				}
			}
		}
	}
	FILE *g = fopen("dijkstra.out","w");
	for (i = 2; i <= n; ++i)fprintf(g,"%d ",(val[i]==INF)?0:val[i]);
	fclose(g);


return 0;
}