#include <iostream>
#include <fstream>
#include <stdio.h>
#include <queue>
const int NMax = 50001;
const int Inf = 50000;

using namespace std;

int N, M;
int d[NMax];
bool inQueue[NMax];
vector<int> graf[NMax], cost[NMax];

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

struct Order
{
    bool operator()(pair<int, int> const& a, pair<int, int> const& b) const
    {
        return a.second > b.second;
    }
};

void Dijkstra(int sursa) {
	std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, Order> q;
	
	for (int i = 0; i < N; i++) {
		if (sursa == i) {
			d[i] = 0;
			q.push(pair<int, int>(i, d[i]));
		} else {
			d[i] = Inf;
			q.push(pair<int, int>(i, d[i]));
		}
		inQueue[i] = true;
	}

	while (!q.empty()) {
		int u = q.top().first;
		q.pop();
		inQueue[u] = false;

		int veciniNod = graf[u].size();
		for (int i = 0; i < veciniNod; i++) {
			int val = graf[u][i];
			if (inQueue[val] == true) {
				if (d[val] > d[u] + cost[u][i]) {
					d[val] = d[u] + cost[u][i];
					q.push(pair<int, int>(val, d[val]));
				}
			}
		}
	}

	for (int i = 0; i < N; i++) {
		if (d[i] == Inf) {
				d[i] = 0;
		}
		if (i != sursa) {
			out << d[i] << " ";
		}
	}	
}

int main() {
	in >> N >> M;

	for (int i = 0; i < M; i++) {
		int x, y, w;
		in >> x >> y >> w;
		graf[x - 1].push_back(y - 1);
		cost[x - 1].push_back(w);
	}

	int k = 0;
	Dijkstra(k);	
	
	return 0;
}