#include <iostream>
#include <fstream>
#include <stdio.h>
#include <queue>
const int NMax = 1001;
const int Inf = 1001;
using namespace std;
int N, M;

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, int Cost[][NMax]) {
	int d[N];
	bool inQueue[N];

	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;

		for (int i = 0; i < N; i++) {
			if (Cost[u][i] != -1) {
				if ((inQueue[i] == true) && (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 (d[i] == Inf) {
			d[i] = 0;
		}
		if (i != sursa) {
			out << d[i] << " ";
		}
	}	
}

int main() {
	int N, M;

	in >> 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;
	Dijkstra(k, Cost);	
	
	return 0;
}