#include <fstream>
#include <vector>
using namespace std;

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

int n,m,heap[50003],rez[50002];
vector <pair<int,int> > a[50002];

void citire () {
	int x,b,c;
	in >> n >> m;
	for (int i = 1; i <= m; ++i) {
		in >> x >> b >> c;
		a[x].push_back(make_pair(b,c));
	}
}

void pop () {
	int aux = heap[1];
	heap[1] = heap[heap[0]];
	heap[heap[0]] = aux;
	
	--heap[0];
	
	//down (1);
}

void push (int x) {
	heap[++heap[0]] = x;
	//up (heap[heap[0]]);
}

void dijkstra () {
	int x;
	
	for (int i = 2; i <= n; ++i) {
		rez[i] = 2000000000;
	}
	
	heap[++heap[0]] = 1;
	
	while (heap[0]) {
		x = heap[1];
		pop ();
		
		for (size_t i = 0; i < a[x].size(); ++i) {
			if (a[x][i].second + rez[x] < rez[a[x][i].first]) {
				rez[a[x][i].first] = a[x][i].second + rez[x];
				push (a[x][i].first);
			}
		}
	}
	
	for (int i = 2; i <= n ;++i) {
		out << rez[i] << ' ';
	}
}

int main () {
	citire ();
	
	dijkstra ();
	
	return 0;
}