#include <fstream>
#include <vector>
using namespace std;
#define inf 100000
long n, m;

int main() {
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");

	fin >> n >> m;

	vector<long> a(m+1,0), b(m+1, 0), c(m+1, 0);
	vector<long> drum(n+1, inf);
	
	for (int i = 1; i <= m; i++) {
		fin >> a[i] >> b[i] >> c[i];
		if (a[i] == 1) {
			drum[b[i]] = c[i];		
		}
	}
	
	bool ok;
		
	do {
		ok = false;
		for (int i = 1; i <= m; i++){
			if (drum[b[i]] > drum[a[i]] + c[i])
				drum[b[i]] = drum[a[i]] + c[i], ok = true;
		}
	
	} while (ok);

	for (int i = 2; i <= n; i++) {
		if (drum[i] == inf) fout << "0 ";
		else fout << drum[i] << " ";
	}
	
	return 0;

}