#include <iostream>
#include <fstream>
#include <stdio.h>
#include <queue>
#define NMax 1000
#define Inf 1000

using namespace std;

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

void Dijkstra(int sursa, int N, int Cost[][NMax]) {
	int d[N];
	bool selectat[N];

	std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int> >, Order> q;
	
	for (int i = 0; i < N; i++) {
		d[i] = -1;
		selectat[i] = false;
	}

	selectat[sursa] = true;

	for (int i = 0; i < N; i++) {
		if (Cost[sursa][i] != -1 && sursa != i) {
			d[i] = Cost[sursa][i];
			q.push(pair<int, int>(i, d[i]));
		} else {
			d[i] = Inf;
		}
	}

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

		for (int i = 0; i < N; i++) {
			if (Cost[u][i] != -1 && u != i) {
				if (!selectat[i] && (d[i] > d[u] + Cost[u][i])) {
					d[i] = d[u] + Cost[u][i];
					q.push(pair<int, int>(i, d[i]));
				}
			}
			
		}
	}
	for (int i = 0; i < N; i++) {
		if (i != sursa) {
			out << d[i] << " ";
		}
	}	
}

int main() {
	//printf("OK\n");
	ifstream in ("dijkstra.in");
	ofstream out ("dijkstra.out");

	printf("OK\n");
	int N, M;

	in >> N >> M;
	//printf("N = %d M = %d\n", N, M);

	int Cost[NMax][NMax];
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
				Cost[i][j] = -1;
		}
	}

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

	int k = 0;
	//printf("OK\n");
	Dijkstra(k, N, Cost);	
	
	return 0;
}