#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
struct edge{
	int nod;
	int val;
	edge(int nod, int val) {
		this->nod = nod;
		this->val = val;
	};	
};
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
vector < vector <edge> > g;
int n, m;
int heap[50005];
int minv[50005];
int heapsize = 0;
int pos[50005];
bool viz[50005];

void swap(int v[], int a, int b) {
	int t;
	t = v[a];
	v[a] = v[b];
	v[b] = t;	
}

void insert(int to, int val) {
	int i, id, t;
	minv[to] = val;
	heap[++heapsize] = to;
	id = heapsize;
	while(id > 1  && minv[heap[id]] < minv[heap[id / 2]]) {
		swap(heap, id, id / 2);
		swap(pos, id, id / 2);
		id = id / 2;
	}
}

void improve(int to, int val) {
	int i, t, id;
	minv[to] = val;
	id = pos[to];
	while(id > 1  && minv[heap[id]] < minv[heap[id / 2]]) {
		swap(heap, id, id / 2);
		swap(pos, id, id / 2);
		id = id / 2;
	}	
}

int minheap() {
	int i, id, t, rez, left, right;
	rez = heap[1];
	heap[1] = heap[heapsize];
	pos[1] = pos[heapsize--];
	i = 1;
	while(i <= heapsize / 2) {
		left = 2 * i;
		right = 2 * i + 1;
		if (minv[heap[left]] < minv[heap[right]])
			id = left;
		else
			id = right;
		if (minv[heap[i]] > minv[heap[id]]) {
			swap(heap, i, id);
			swap(pos, i, id);
			i = id;
		} else {
			break;	
		}
	}
	return rez;	
}

void dijkstra() {
	int i, mn, to, val;
	edge son(0,0);
	insert(1, 0);
	while(heapsize > 0) {
		mn = minheap();
		viz[mn] = 1;
		for (i = 0; i < g[mn].size(); i++) {
			to = g[mn][i].nod;
			val = g[mn][i].val;
			if (minv[to] >= 0) {
				if (minv[to] > minv[mn] + val) {
					improve(to, minv[mn] + val);
				}
			} else {
				insert(to, val + minv[mn]);	
			}
		}
	}
	for (i = 2; i <= n; i++) {
		fo << minv[i] << ' ';
	}
	return;
}

int main() {
	int i, x, y, c;
	fi >> n >> m;
	g.resize(n + 1);
	for (i = 0; i <= n; i++) {
		heap[i] = -90;
		pos[i] = 0;
		minv[i] = -60;
	}
	for (i = 0; i < m; i++) {
		fi >> x >> y >> c;
		g[x].push_back(edge(y, c));
	}
	dijkstra();
	fi.close();
	fo.close();
	return 0;	
}