//#include "pch.h"
#include<iostream>
#include<vector>
#include<fstream>
#include<queue>
#include<climits>
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector<int> dist;
vector<bool> viz;
vector<pair<int,int>> graf[50005];
void dijkstra(vector<pair<int,int>> graf[], int start, int N) {
	for (int i = 0; i < N; i++) {
		dist.push_back(INT_MAX);
		viz.push_back(false);
	}
	dist[start] = 0;
	priority_queue<pair<int,int>> pq;
	pq.push(make_pair(0,start));
	while (!pq.empty()) {
	
		int u;
		u= pq.top().second;
		pq.pop();
		vector< pair<int, int> >::iterator i;
		
		for (i = graf[u].begin(); i != graf[u].end(); i++) {
			int nod = (*i).second;
			int cost = -(*i).first;
				if (dist[nod] > dist[u] + cost) {
					dist[nod] = dist[u] + cost;
					pq.push(make_pair(-dist[nod], nod));
					
				}


		}

	}

}
int main()
{
	int N, M, A, B, C;
	f >> N >> M;
	for (int i = 0; i <= M; i++) {
		f >> A >> B >> C;
		graf[A-1].push_back(make_pair(-C, B-1));

	}

	dijkstra(graf, 0, N);

	for (int i = 1; i < N; i++)
		cout << dist[i] << ' ';
	
	
	return 0;
}