#include <cstdio>
#include <cassert>
#include <vector>
#include <list>
#include <set>
using namespace std;
#define INFINIT 10000
#define _submit
#ifdef _submit
#define InFile "dijkstra.in"
#define OutFile "dijkstra.out"
#else
#define InFile "fis.in"
#define OutFile "fis.out"
#endif

typedef unsigned char uchar;
typedef unsigned int uint;
typedef long long LL;
typedef unsigned long long ULL;
typedef unsigned short ushort;

class graph {
private:
	vector < list< pair<int, int> > > adiacence;
public:
	graph();
	graph(int);
	void newNodes(int);
	void newMuchie(int, int, int);
	void removeDuplicates();
	vector<int> Dijkstra(int);
	int size();
};

graph::graph() {
	adiacence.reserve(1010);
}

graph::graph(int n) {
	adiacence.resize(n);
}

void graph::newNodes(int n) {
	adiacence.resize(adiacence.size() + n);
}

void graph::newMuchie(int n1, int n2, int w) {
	adiacence[n1].push_back({ n2, w });
}

void graph::removeDuplicates() {
	for (auto i = adiacence.begin(); i<adiacence.end(); ++i)
		i->unique();
}

int graph::size() {
	return adiacence.size();
}

vector<int> graph::Dijkstra(int startNod) {
	vector<int> dist(size());
	dist[startNod] = 0;
	set< pair<int, int> > unvisited;
	unvisited.insert({ 0, startNod });
	for (int i = 0; i<size(); i++) {
		if (i != startNod) {
			dist[i] = INFINIT;
			unvisited.insert({ INFINIT, i });
		}
	}

	while (!unvisited.empty()) {
		set< pair<int, int> >::iterator it = unvisited.lower_bound({ -1, -1 });
		int u = it->second;
		unvisited.erase(it);
		for (auto i = adiacence[u].begin(); i != adiacence[u].end(); i++) {
			int alt = dist[u] + i->second;
			if (alt < dist[i->first]) {
				it = unvisited.find({ dist[i->first], i->first });
				if (it != unvisited.end()) {
					pair<int, int> p = *it;
					p.first = alt;
					unvisited.erase(it);
					unvisited.insert(p);
					dist[i->first] = alt;
				}
			}
		}
	}

	return dist;
}

int main() {
	assert(freopen(InFile, "r", stdin));
	assert(freopen(OutFile, "w", stdout));
	int N, M;
	scanf("%d%d", &N, &M);
	graph *G = new graph(N);
	for (int i = 0; i < M; i++) {
		int x, y, w;
		scanf("%d%d%d", &x, &y, &w);
		G->newMuchie(x - 1, y - 1, w);
	}

	vector<int> v = G->Dijkstra(0);
	for (auto i = v.begin() + 1; i != v.end(); ++i)
		printf("%d ", *i);
	return 0;
}