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

#define oo 2147483647
#define to first
#define cost second
#define mp make_pair

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

typedef vector<pair<int,int> >:: iterator it;

int N,M;
vector<pair<int,int> >a[50001];
long long d[50001];
bool in[50001];

struct cmp
{	bool operator ()(int i,int j)
	{	if(d[i] < d[j]) return 1;
		return 0;
	}
};
priority_queue<int,vector<int>,cmp>q;

int main()
{	int i,j,x,y,c;
	fscanf(f,"%d %d",&N,&M);
	for(i = 1; i <= M; i++)
	{	fscanf(f,"%d %d %d",&x,&y,&c);
		a[x].push_back(mp(y,c));
	}
	for(i = 2; i <= N; i++)
		d[i] = oo;
	d[1] = 0; q.push(1); in[1] = 1;
	while(!q.empty())
	{	x = q.top(); q.pop(); in[x] = 0;
		for(it k = a[x].begin(); k != a[x].end(); k++)
			if(d[k->to] > d[x] + k->cost)
			{	d[k->to] = d[x] + k->cost;
				if(!in[k->to])
				{	in[k->to] = 1; q.push(k->to); }
			}
	}
	for(i = 2; i <= N; i++)
		if(d[i] != oo) fprintf(g,"%d ",d[i]);
		else fprintf(g,"%d ",0);
	fclose(f);
	fclose(g);
	return 0;
}