#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define NMAX 50005
#define inf 0x3f3f3f3f
using namespace std;

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

struct Nod {
	int nr, dist;
	Nod (int x, int y) {
		nr = x;
		dist = y;
	}
	bool operator<(const Nod &altu) const{
		return dist > altu.dist;	
	}
};

vector <pair<int, int> > G[NMAX];
bitset <NMAX> verif;
priority_queue <Nod> pq;
int n, m, dist[NMAX];

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));
	}
	for (int i = 2; i <= n; ++i) {
		dist[i] = inf;
	}
	pq.push(Nod(1,0));
	while (!pq.empty()) {
		Nod nod = pq.top();
		pq.pop();
		if (verif[nod.nr]) {
			continue;	
		}
		verif[nod.nr] = 1;
		for (int i = 0; i < G[nod.nr].size(); ++i) {
			if (!verif[G[nod.nr][i].first]) {
				Nod nou = Nod(G[nod.nr][i].first, G[nod.nr][i].second);
				nou.dist += nod.dist;
				if (nou.dist < dist[nou.nr]) {
					dist[nou.nr] = nou.dist;
					pq.push(nou);
				}
			}
		}
	}
	for (int i = 2; i <= n; ++i) {
		fout << dist[i] << " ";	
	}
	
	return 0;	
}