#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() {
	dist[1] = 0;
	pq.push(P(0, 1));
	while (!pq.empty()) {
		P teto = pq.top();
		pq.pop();
		int tav = teto.first;
		int csp = teto.second;
		if (teto.first != dist[teto.second]) continue;
		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 });
			}
		}
		
	}
}

void write() {
	for (int i = 2; i <= n; i++) {
		if (dist[i] == INF) fout << 0 << " ";
		else fout << dist[i] << " ";
	}
}

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