#include <cstdio>
#include <cassert>
#include <vector>
#include <set>
#include <queue>
using namespace std;

const int N = 50000;
const int INF = 0x3f3f3f3f;

int n,m;
vector< pair<int,int> > g[N];
int d[N];
int r[N];

void dijkstra() {
	set< pair<int, int> > s;
	d[0] = 0;
	for (int i = 1; i < n; ++i) d[i] = INF;
	for (s.insert(make_pair(0,0)); !s.empty(); s.erase(s.begin())) {
		int c = s.begin()->second;
		vector< pair<int,int> > &cg = g[c];
		for (int i = 0; i < cg.size(); ++i) {
			int nd = d[c] + cg[i].second;
			if (d[cg[i].first] > nd) {
				if (d[cg[i].first] != INF) s.erase(s.find(make_pair(d[cg[i].first],cg[i].first)));
				d[cg[i].first] = nd;
				s.insert(make_pair(d[cg[i].first],cg[i].first));
			}
		}
	}
}

int main() {
	freopen("dijkstra.in","rt",stdin);
	freopen("dijkstra.out","wt",stdout);
	scanf("%d %d",&n,&m);
	for (int i = 0; i < m; ++i) {
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		--a; --b;
		g[a].push_back(make_pair(b,c));
	}
	dijkstra();
/*	for (int i = 1; i < n; ++i) printf("%4d ",i);
	printf("\n");
	for (int i = 1; i < n; ++i) printf("%4d ",(r[i]) ? 1 : -1);
	printf("\n");
	for (int i = 1; i < n; ++i) printf("%4d ",(d[i] == INF) ? 0 : d[i]);
	printf("\n");*/
	for (int i = 1; i < n; ++i) printf("%d ",(d[i] == INF) ? 0 : d[i]);
	printf("\n");
	return 0;
}