#include<stdio.h>
#include<vector>
#include<queue>
#define nmax 50003

using namespace std;

typedef pair<int, int> p;

priority_queue<p, vector<p>, greater<p> > h;
vector<p> g[nmax];
int n,m,i,j,a,b,d, drum[nmax], inf=2<<20, viz[nmax];


int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	scanf("%d %d", &n, &m);
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d", &a, &b, &d);
		g[a].push_back(make_pair(d,b));
	}
	vector<p>::iterator it;
	for(i=1;i<=n;i++)
		drum[i]=inf;
	drum[1]=0;
	h.push(make_pair(0,1));
	while(!h.empty())
	{
		while(!h.empty()&&viz[h.top().second]==1)
			h.pop();
		if(h.empty())
			break;
		d=h.top().first;
		a=h.top().second;
		h.pop();
		viz[a]=1;
		for(it=g[a].begin();it!=g[a].end();it++)
			if(d+it->first<drum[it->second])
			{
				drum[it->second]=d+it->first;
				h.push(make_pair(drum[it->second], it->second));
			}
	}
	for(i=2;i<=n;i++)
		printf("%d ", drum[i]);
	printf("\n");
	return 0;
}