// Dijkstra with buckets
// Dijkstra cu galeti
#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() 
{
	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() 
{
	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  // ,,relaxam'' toti vecinii lui u 
	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 // eliminam v din galeata veche
				int t = dist[v] % (C + 1);
			//	buckets[t].remove(v);
			}
			// add v to its new bucket   // adaugam v in galeata lui noua
			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() 
{
	read_graph();
	dijkstra();
    
	for (int i = 1; i < N; ++ i)
	{
		if (dist[i] == INFI)
			fout << "0 ";
		else
			fout << dist[i] << " ";
	}
	fout << endl;
    
	return 0;
}