//#include<stdio.h>
#include<queue>
#include<vector>
#include<fstream>
using namespace std;

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

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

ifstream f(in);
ofstream g(out);

#define pb push_back
#define mp make_pair

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

void solve()
	{
		int i, val, x;
		for(i = 2 ; i <= n ; ++i)d[i] = inf;
		S.push(mp(0, 1));
		while( S.size() )
		{
			val = -S.top().first , x = S.top().second;
			S.pop();
			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.push(mp(-d[ G[x][i]], G[x][i]));
		}
}
			

int main()
	{
	//	freopen(in,"r",stdin);
	//	freopen(out,"w", stdout);
	//	scanf("%d%d", &n, &m);
		f>>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);
			f>>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]);
			g<<((d[i] == inf ) ? 0 : d[i])<<" " ;
		return 0;
}