#include <iostream>
#include <fstream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <iterator>
#include <queue>
#include <functional>
#define INF 2000000000

using namespace std;

int n, m, x0;
int dist[50001], last[50001];
bool viz[50001];
vector<pair<int, int> > c[50001];

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

void citire();

priority_queue<int, vector<pair<int, int> >, less<pair<int, int> > > pq; // (dist, varf)

int main() {
	int u, i;

	citire();
	
	while (!pq.empty()) {
		u = pq.top().second; // varful de start
		pq.pop();
		if (viz[u] == false) {
			viz[u] = true;

			for (i = 0; i < c[u].size(); ++i) {
				if (dist[c[u][i].second] > dist[u] + c[u][i].first) { 
					dist[c[u][i].second] = dist[u] + c[u][i].first;
					pq.push({ dist[c[u][i].second], c[u][i].second });
				}
			}
		}
	}

	for (i = 2; i <= n; ++i)
		fout << (dist[i] == INF ? 0 : dist[i]) << ' ';

	return 0;
}

void citire() {
	int x, y, cost, i;

	fin >> n >> m;

	for (i = 1; i <= n; ++i) {
		dist[i] = INF;
		last[i] = -1;
	}

	for (i = 1; i <= m; ++i) {
		fin >> x >> y >> cost;
		c[x].push_back({ cost, y });
	}

	dist[1] = 0;

	pq.push({ 0, 1});
}