#include <iostream>
#include <fstream>
#include <functional>
#include <queue>
#include <fstream>
#include <vector>
#include <limits>

using namespace std;

ifstream fin("Dijkstra.in");
ofstream fout("Dijkstra.out");

typedef pair<int, int> P;
const int INF = numeric_limits<int>::max() / 2;
priority_queue<P, vector<P>, greater <P> > pq;
vector<vector<P>> a;
vector<int> dist;
int n, m;

void read() {
	fin >> n >> m;
	a.resize(n + 1);
	int p, q, r;
	for (int i = 1; i <= m; i++) {
		fin >> p >> q >> r;
		a[p].push_back(P(q,r));
	}
	dist.resize(n + 1,INF);
}

void solve() {
	pq.push(P(0, 1));
	while (!pq.empty()) {
		P teto = pq.top();
		int tav = teto.first;
		int csp = teto.second;
		for (auto e : a[csp]) {
			int ujtav = e.second;
			int ujcsp = e.first;
			if (dist[ujcsp] > tav + ujtav) {
				dist[ujcsp] = tav + ujtav;
				pq.push(P{ ujtav + tav,ujcsp });
			}
		}
		pq.pop();
	}
}

void write() {
	for (auto& e : dist)
		if (e != INF) fout << e << " ";
}

int main() {
	read();
	solve();
	write();
}