// Dijkstra with buckets

#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <cassert>

#define INFI 0x3f3f3f3f

using namespace std;

typedef pair<int, int> edge;

int M, N, C;
vector< list<int> > buckets;
vector< vector<edge> > adj;
vector<int> dist;
int pos, final;

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

void read_graph(void) {
	fin >> N >> M;
    
	vector< edge > v;
	adj.resize(N, v);
    
	C = 0;
    
	int a, b, c;
	for (int i = 0; i < M; ++ i) {
		fin >> a >> b >> c;
		-- a; -- b;
        
		edge e = make_pair(b, c);
		adj[a].push_back(e);
        
		if (c > C)
            C = c;
	}
}

int next_bucket(void) {
	for (int i = 0; i < C + 1; ++ i) {
		int k = (pos + i) % (C + 1);
        
		if (!buckets[k].empty())
			return k;
	}
    
	return -1;
}

void relax_neighbours(int u) {
	int n = adj[u].size();
    
	// relax all of u's neighbours
	for (int i = 0; i < n; ++ i) {
		edge e = adj[u][i];
		int v = e.first;
		int len = e.second;
        
		if (dist[v] > dist[u] + len) {
			if (dist[v] != INFI) {
				// remove v from the old bucket
				int t = dist[v] % (C + 1);
		//		buckets[t].remove(v);
			}
            
			// add v to its new bucket
			dist[v] = dist[u] + len;
			int t = dist[v] % (C + 1);
			buckets[t].push_back(v);
		}
	}
}

void dijkstra(void) {
	list<int> l;
	buckets.resize(C + 1, l);
    
	dist.resize(N, INFI);
	dist[0] = pos = 0;
	buckets[0].push_back(0);
	final = N;
    
	while (1) {//final > 0) {
		int k = next_bucket();
		if (k == -1)
			break;
        
		while (!buckets[k].empty()) {
			int u = buckets[k].back();
			buckets[k].pop_back();
			relax_neighbours(u);
			-- final;
		}
        
		pos = (k + 1) % (C + 1);
	}
}

int main(void) {
	read_graph();
	dijkstra();
    
	for (int i = 1; i < N; ++ i) {
		if (dist[i] == INFI)
			fout << "0 ";
		else
			fout << dist[i] << " ";
	}
	fout << endl;
    
	return 0;
}