#include <cstdio>
#include <vector>
#include <list>
#include <set>
#define Nmax 50001
#define nod first
#define cost second
#define inf 2000000000

using namespace std;

vector< int > d;
vector< list< pair< int,int > > > g(Nmax, list< pair< int,int > >());
vector<bool> uz;
struct Comp { bool operator()(int i, int j){ return d[i] < d[j]; } };
set< int,Comp > Q;
int N, M, x, y, c, i; 

int main()
 {
 	freopen("dijkstra.in", "r", stdin);
	scanf("%d %d\n", &N, &M);
	d.assign(N+3,inf);
	uz.assign(N+3,false);
	for (i = 1; i<=M; ++i)
	{
		scanf("%d %d %d\n", &x, &y, &c);
		g[x].push_back(make_pair(y,c));
	}
	d[1] = 0;
	uz[1] = true;
	Q.insert(1);
	while (!Q.empty())
	{
		x = *Q.begin();
		uz[x] = false;
		Q.erase(Q.begin());
		for (list< pair< int,int > >::iterator it = g[x].begin(); it != g[x].end(); ++it)
		{
			if (d[it->nod] > d[x] + it->cost)
			{
				d[it->nod] = d[x] + it->cost;
				if (uz[it->nod]) Q.erase(it->nod);
				uz[it->nod] = true;
				Q.insert(it->nod);
			}
		}
	}
	freopen("dijkstra.out", "w", stdout);
	for (i = 2; i<=N; ++i) printf("%d ", d[i]==inf?0:d[i]);
	return 0;
 }