#include <fstream> 
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

#define in "dijkstra.in"
#define out "dijkstra.out"

#define N 50005
#define INF 1 << 30

struct nod {
	int y, c;
};

nod init (int y, int c) {
	nod a;
	a.y = y;
	a.c = c;
	return a;
}

vector <nod> LIST[N];
vector <bool> M (N, 0);
vector <int> d (N, INF);
int n, m;

int main ()
{
	ifstream fin (in);
	fin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int x, y, c;
		fin >> x >> y >> c;
		LIST[x].push_back (init (y, c));
	}
	fin.close();
	
	d[1] = 0;
	for (int w = 0; w < n; ++w) {
		int min = INF, x;
		for (int j = 1; j <= n; ++j)
			if (d[j] < min && !M[j])
				min = d[j], x = j;
		M[x] = 1;
		for (unsigned i = 0; i < LIST[x].size(); ++i)
			if (d[LIST[x][i].y] > d[x] + LIST[x][i].c)
				d[LIST[x][i].y] = d[x] + LIST[x][i].c;
	}
	
	ofstream fout (out);
	for (int i = 2; i <= n; ++i) 
		fout << ((d[i] == INF) ? 0 : d[i]) << " ";
	fout.close();
	return 0;
}