#include<stdio.h>
#include<set>
#include<vector>
using namespace std;

const char in[]="dijkstra.in";
const char out[]="dijkstra.out";

const int inf = 1 << 30;
const int MaxN = 50005;

#define pb push_back
#define mp make_pair

int n, m, d[MaxN];
vector<int> G[MaxN], C[MaxN];
set< pair<int,int> >S;

void solve()
	{
		int i, val, x;
		for(i = 2 ; i <= n ; ++i)d[i] = inf;
		S.insert(mp(0, 1));
		while( S.size() )
		{
			val = (*S.begin()).first , x = (*S.begin()).second;
			S.erase(*S.begin());
			for(i = 0 ; i < G[x].size() ; ++i)
				if(d[ G[x][i] ] > val + C[x][i])
					d[ G[x][i] ] = val + C[x][i], S.insert(mp(d[ G[x][i] ], G[x][i]));
		}
}
			

int main()
	{
		freopen(in,"r",stdin);
		freopen(out,"w", stdout);
		scanf("%d%d", &n, &m);
		int x, y, c;
		for(int i = 1 ; i <= m ; ++i)
			scanf("%d%d%d", &x, &y, &c), G[x].pb(y), C[x].pb(c);
		solve();
		for(int i = 2 ; i <= n ; ++i)
			printf("%d ", d[i] == inf ? 0 : d[i]);
		return 0;
}