#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define NMAX 50005
#define inf 0x3f3f3f3f

using namespace std;

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

int n, m, dist[NMAX];
struct Nod {
	int nod, cost;
	Nod (int x, int y) {
		nod = x;
		cost = y;
	}
	bool operator<(const Nod &altu) const {
		return cost < altu.cost;
	}
};
vector <pair<int, int> > g[NMAX];
priority_queue <Nod > pq;

int main()
{
	fin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int x, y, z;
		fin >> x >> y >> z;
		g[x].push_back(make_pair(y,z));
	}
	memset(dist, inf, sizeof(dist));
	dist[1] = 0;
	Nod start = Nod(1, 0);
	pq.push(start);
	while (!pq.empty()){
		Nod node = pq.top();
		pq.pop();
		if (node.cost > dist[node.nod]) {
			continue;	
		}
		for (int i = 0; i < g[node.nod].size(); ++i) {
			Nod newnode = Nod(g[node.nod][i].first, g[node.nod][i].second);
			if (dist[newnode.nod] > newnode.cost + dist[node.nod]) {
				dist[newnode.nod] = newnode.cost + dist[node.nod];
				newnode.cost = dist[newnode.nod];
				pq.push(newnode);
			}
		}
	}
	for (int i = 2; i <= n; ++i) {
		if (dist[i] == inf) {
			dist[i] = 0;	
		}
		fout << dist[i] << ' ';
	}
	return 0;	
}