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

using namespace std;

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

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
const int inf = 2e9;

int n, m;
vii gf[100001];
bool viz[100001];
int d[100001];
priority_queue<ii, vii, greater<ii>> pq;

void dijkstra(int s) {
	for (int i = 1; i <= n; i++)
		d[i] = inf;
	d[s] = 0;
	pq.push({ d[s], s });
	while (!pq.empty()) {
		int vn = pq.top().second;
		pq.pop();
		if (viz[vn])
			continue;
		viz[vn] = 1;
		for (ii i : gf[vn]) {
			int vvc = i.first;
			int vvn = i.second;
			if (!viz[vvn] && d[vvn] > d[vn] + vvc) {
				d[vvn] = d[vn] + vvc;
				pq.push({ d[vvn], vvn });
			}
		}
	}
	
}

int main() {
	fin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y, c;
		fin >> x >> y >> c;
		gf[x].push_back({c, y});
	}
	dijkstra(1);
	for (int i = 2; i <= n; i++)
        if (d[i] == inf)
            fout << "0 ";
        else fout << d[i] << " ";
	return 0;
}