#include <cstdio>
#include <set>
#include <vector>
#include <utility>
#define Nmax 50001
#define nod first
#define cost second

using namespace std;

vector< int > d;
vector< vector< pair< int,int > > > g(Nmax, vector< pair< int,int > >() );
struct compare{ bool operator()( int x, int y ) { return d[x] < d[y]; } };
set< int, compare> Q;
int N, M, x, y, z, i;

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