#include <cstdio>
#include <vector>
#include <list>
#include <set>
#define Nmax 50001
#define MAXINT 0x3f3f3f3f

using namespace std;

vector< int > d;
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]; }};
multiset<int, compare> Q;
int N, M, x, y, z;

int main()
{
	for (freopen("dijkstra.in", "r", stdin), scanf("%d %d\n", &N, &M), d.assign(N+1,MAXINT); 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(); uz[*Q.begin()] = false, Q.erase(Q.begin()))
	{
		x = *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);
				else 
					uz[it->first] = true;
				Q.insert(it->first);
			}
	}
	freopen("dijkstra.out", "w", stdout);
	for (vector<int>::iterator it = d.begin() + 2; it !=d.end(); ++it) printf("%d ", *it==MAXINT? 0 : *it);
	return 0;
}