#include <iostream>
#include <fstream>
#include <vector>

#define INF -1
#define NEW 0
#define FOUND 1
#define FINISHED 2

using namespace std;

typedef struct {
	int id;
	int c;
} Edge;

typedef struct {
	int n;
	vector < vector <Edge> > V;
} Graph;

typedef struct {
	int n;
	Edge *v;
	int *index;
} Heap;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
Heap H = {0, NULL, NULL};
Graph G;
int *d;
int *visited;

void swap (int i1, int i2) {
	H.index[H.v[i1].id] = i2;
	H.index[H.v[i2].id] = i1;
	
	Edge c = H.v[i1];
	H.v[i1] = H.v[i2];
	H.v[i2] = c;
}

void addHeap (Edge e) {
	int i = H.n;
	H.v[i] = e;
	
	while (i >= 0 && H.v[i].c < H.v[(i-1)/2].c) {
		int aux = (i-1)/2;
		swap(i, aux);
		i = aux;
	}
	
	++(H.n);
}

void popHeap () {
	--(H.n);
	H.v[0] = H.v[H.n];	
	
	int i = 0, ok = 0;
	while(!ok) {
		int l = 2*i+1, r = 2*i+2;
		if (r < H.n && (H.v[i].c > H.v[l].c || H.v[i].c > H.v[r].c)) {
			if (H.v[l].c < H.v[r].c) {
				swap(i, l);
				i = l;
			} else {
				swap(i, r);
				i = r;
			}
		} else if (l < H.n && H.v[i].c > H.v[l].c) {
			swap(i, l);
			i = l;
		} else {
			ok = 1;
		}
	}
	
}

void modCost (int id, int nc) {
	int i = H.index[id];
	H.v[i].c = nc;
	
	while (i >= 0 && H.v[i].c < H.v[(i-1)/2].c) {
		int aux = (i-1)/2;
		swap(i, aux);
		i = aux;
	}
}
	
void read() {
	in >> G.n;
	
	H.v = new Edge[G.n];
	H.index = new int[G.n + 1];
	
	for (int i = 1; i <= G.n; ++i) {
		vector <Edge> a;
		G.V.push_back(a);
	}
	
	int m;
	in >> m;
	
	for (int i = 0; i < m; ++i) {
		int x, y, z;
		in >> x >> y >> z;
		Edge aux = {y, z};
		G.V[x].push_back(aux);
	}
}

void dijkstra () {
	d = new int[G.n + 1];
	for (int i = 0; i <= G.n; ++i) {
		d[i] = INF;
	}
	
	visited = new int[G.n+1]();
	visited[1] = FINISHED;
	
	for (unsigned int i = 0; i < G.V[1].size(); ++i) {
		addHeap(G.V[1][i]);
		d[G.V[1][i].id] = G.V[1][i].c;
		visited[G.V[1][i].id] = FOUND;
	}
	
	while (H.n) {
		int id = H.v[0].id;
		popHeap();
		
		for (unsigned int i = 0; i < G.V[id].size(); ++i) {
			int test = d[id] + G.V[id][i].c;
			if (visited[G.V[id][i].id] == NEW) {
				d[G.V[id][i].id] = test;
				addHeap(G.V[id][i]); 
				visited[G.V[id][i].id] = FOUND;
			} else if (d[G.V[id][i].id] == INF || d[G.V[id][i].id] > test) {
				d[G.V[id][i].id] = test;
				modCost(G.V[id][i].id, test);
			}
		}
		
		visited[id] = FINISHED;
	}
}
	
int main(void) {
	read();
	
	dijkstra();
	
	for (int i = 2; i <= G.n; ++i) {
		if (d[i] == INF) {
			out << 0 << " ";
		} else {
			out << d[i] << " ";
		}	
	}
	
	return 0;
}