#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <queue>
#include <cstring>
#include <set>
#include <cctype>
#include <algorithm>
using namespace std;

template <class T> void readNum(T &nr) {
	nr = 0;
	T sign = 1;
	char c;
	while (!isdigit(c = getchar()))
		(c == '-') && (sign = -1);
	do {
		nr = nr * 10 + c - '0';
	} while (isdigit(c = getchar()));
	nr *= sign;
}

class graph {
private:
	vector< vector< pair<int, int> > > ngh;
public:
	graph() {
		ngh.reserve(210);
	}
	void clear() {
		ngh.clear();
	}
	void resize(int N) {
		ngh.resize(N);
	}
	void newEdge(int n1, int n2, int dist) {
		ngh[n1].push_back(make_pair(n2, dist));
		//ngh[n2].push_back(make_pair(n1, dist));
	}
	int kDijkstra(int nod, int K, vector<int>& dist, vector<int>& cdist) {
		int N = ngh.size();
		memset(&dist[0], 0x3f, dist.size() * sizeof(dist[0]));
		dist[nod] = 0;
		priority_queue< pair<int, int> > Q;
		Q.push(make_pair(dist[nod], nod));
		while (!Q.empty()) {
			if (dist[Q.top().second] != -Q.top().first) {
				Q.pop();
				continue;
			}
			int t = Q.top().second;
			Q.pop();
			for (vector< pair<int, int> >::iterator i = ngh[t].begin(); i != ngh[t].end(); ++i)
			if (dist[t] + i->second < dist[i->first]) {
				dist[i->first] = dist[t] + i->second;
				Q.push(make_pair(-dist[i->first], i->first));
			}
		}
		for (auto i = dist.begin() + 1; i != dist.end(); ++i)
			printf("%d ", ((*i) != 0x3f3f3f3f) ? *i : 0);
		/*memcpy(&cdist[0], &dist[0], cdist.size() * sizeof(cdist[0]));
		sort(dist.begin(), dist.end());
		int lookfor = dist[K];
		for (vector<int>::iterator i = cdist.begin(); i != cdist.end(); ++i)
		if (*i == lookfor)
			return distance(cdist.begin(), i);*/
		return 0;
	}
};

int main() {
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	graph G;
	vector<int> dst, cdst;
	while (true) {
		int N, M;
		readNum(N);
		if (!N)
			break;
		G.clear(), G.resize(N), dst.resize(N); cdst.resize(N);
		readNum(M);
		for (int i = 0; i < M; i++) {
			int a, b, c;
			readNum(a); readNum(b); readNum(c);
			--a, --b;
			G.newEdge(a, b, c);
		}
		G.kDijkstra(0, 0, dst, cdst);
		//int K; readNum(K);
		//printf("%d\n", G.kDijkstra(0, K, dst, cdst));
		break;
	}
	return 0;
}