#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <fstream>
using namespace std;

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

void dijkstra(int n, vector<vector<pair<int, int>>> &graf, vector<long long> &dist)
{
	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;

	dist[1] = 0;
	pq.push({0, 1});

	while (!pq.empty()){
		long long d = pq.top().first;
		int nod = pq.top().second;
		pq.pop();

		if (d != dist[nod]){
			continue;
		}

		for (auto grafi : graf[nod]){
			int vecin = grafi.first;
			int cost = grafi.second;

			if (dist[vecin] > dist[nod] + cost){

				dist[vecin] = dist[nod] + cost;

				pq.push({dist[vecin], vecin});

			}
		}
	}
}

vector<vector<pair<int, int>>> graf;
vector<long long> dist;

int main()
{
	int n, m;
	fin >> n >> m;

	graf.resize(n + 1);
	dist.resize(n + 1, LLONG_MAX);

	int x, y, z;

	for (int i = 1; i <= m; i++){
		fin >> x >> y >> z;

		graf[x].push_back({y, z});
	}

	dijkstra(n, graf, dist);

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

		fout << ' ';
	}

	fout << '\n';

	return 0;
}