#include<stdio.h>
#include<vector>
#define nmax 50010

using namespace std;

vector< pair<int, int> > v[nmax];
int n,m,i,j,k,x,y,z, minim=0, index;
int way[nmax];
int viz[nmax];



int main()
{
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	scanf("%d %d", &n, &m);
	pair<int, int> p;
	viz[1]=1;
	for(i=1;i<=n;i++)
		way[i]=999999;
	for(i=1;i<=m;i++)
	{
		scanf("%d %d %d", &x, &y, &z);
		p=make_pair(y,z);
		v[x].push_back(p);		
	}
	for(i=0;i<v[1].size();i++)
		way[v[1][i].first]=v[1][i].second;
	while(minim!=999999)
	{
		minim=999999;
		for(i=1;i<=n;i++)
			if(viz[i]==0&&way[i]<minim)
				minim=way[i],index=i;
		viz[index]=1;
		for(i=0;i<v[index].size()&&minim!=999999;i++)
			if(way[v[index][i].first]==999999||way[v[index][i].first]>way[index]+v[index][i].second)
				way[v[index][i].first]=way[index]+v[index][i].second;

	}
	for(i=2;i<=n;i++)
		printf("%d ", way[i]);
	return 0;
}