#include<iostream>
#include<vector>
#include<fstream>
#define INFN 1000000000

using namespace std;

struct edge {
	int to;
	int val;
};

int n;
int m;

int minim(char viz[], int dist[]) {
	int min = INFN;
	int index = -1;
	for (int i = 1; i <= n; i++) {
		if (!viz[i] && dist[i] < min) {
			min = dist[i];
			index = i;
		}
	}
	return index;
}

int main() {
	ifstream in("dijkstra.in");
	ofstream out("dijkstra.out");
	
	in >> n >> m;
	
	int a, b, c;
	
	vector< edge > v[n + 1];
	
	edge x;
	for (int i = 0; i < m; i++) {
		in >> a >> b >> c;
		x.to = b;
		x.val = c;
		v[a].push_back(x);
	}
	
	char viz[n + 1];
	int dist[n + 1];
	for (int i = 1; i <= n; i++) {
		dist[i] = INFN;
		viz[i] = 0;
	}
	dist[1] = 0;
	
	int k = 0;
	int min, index;
	while (k < n) {
		index = minim(viz, dist);
		if (index == -1) break;
		for(int i = 0; i < v[index].size(); i++) {
			x = v[index][i];
			if (viz[x.to] == 0 && dist[index] + x.val < dist[x.to]) {
				dist[x.to] = dist[index] + x.val;
			}
		}
		viz[index] = 1;
		k++;
	}
	
	for (int i = 2; i <= n; i++) {
		if (dist[i] == INFN)
			out << 0 << " ";
		else
			out << dist[i] << " ";
	}
	
	in.close();
	out.close();
	return 0;	
}