#include <cstdio>
#include <values.h>
#include <vector>
#include <list>
#include <set>
#define Nmax 50001

using namespace std;

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

int main()
{
	for (freopen("dijkstra.in", "r", stdin), scanf("%d %d\n", &N, &M); M; --M)
	{
		scanf("%d %d %d\n", &x, &y, &z);
		g[x].push_back(make_pair(y,z));
	}
	for (d[1] = 0, uz[1] = true, Q.insert(1); !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[x] + it->second < d[it->first])
			{
				d[it->first] = d[x] + it->second;
				if (uz[it->first])
					Q.erase(it->first);
				uz[it->first] = true;
				Q.insert(it->first);
			}
	}
	freopen("dijkstra.out", "w", stdout);
	for (int i = 2; i<=N; ++i) printf("%d ", d[i]==MAXINT?0:d[i]);
	return 0;
}