#include <bits/stdc++.h>
#include <chrono>

#define INFI 0x3f3f3f3f

using namespace std;

struct graf{
    int dest, cost;
};

int M, N, C;
graf e;
vector< unordered_set<int> > buckets;
vector< vector<graf> > adj;
vector<int> d;
int pos, final;

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

void read_graph(void) {
    int i;
	fin >> N >> M;

	vector< graf > v;
	adj.resize(N, v);

	C = 0;

	int a, b, c;
	for (i = 0; i < M; ++ i) {
		fin >> a >> b >> c;
		-- a; -- b;
        e.dest = b, e.cost = 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();

	for (int i = 0; i < n; ++ i) {
		graf e = adj[u][i];
		int v = e.dest;
		int len = e.cost;

		if (d[v] > d[u] + len) {
			if (d[v] != INFI) {

				int t = d[v] % (C + 1);
				buckets[t].erase(v);
			}


			d[v] = d[u] + len;
			int t = d[v] % (C + 1);
			buckets[t].insert(v);
		}
	}
}

void dijkstra(void) {
	unordered_set <int> l;
	buckets.resize(C + 1, l);

	d.resize(N, INFI);
	d[0] = pos = 0;
	buckets[0].insert(0);
	final = N;

	while (final > 0) {
		int k = next_bucket();
		if (k == -1)
			break;

		while (!buckets[k].empty()) {
			int u = *(buckets[k].begin());
			buckets[k].erase(u);
			relax_neighbours(u);
			-- final;
		}
		pos = (k + 1) % (C + 1);
	}
}

int main() {
	read_graph();
	dijkstra();


    for(int i = 0; i < N; i++)
    {
        if(d[i] != INFI)
            fout << d[i] << ' ';
        else
            fout << 0 << ' ';
    }
	return 0;
}