#include <fstream>
#include <map>
#include <vector>
#include <queue>
#include <limits>

#define nm 50001

using namespace std;

vector<int> V[nm];
vector<int> F[nm];
queue<int> Q;
int N;

int main() {

	int x, y, l, M, i;
	int D[nm];
	bool I[nm];

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

	fin >> N >> M;

	// add edges
	while (M--) {

		fin >> x >> y >> l;
		V[x].push_back(y);
		F[x].push_back(l);

	}

	// set initial distances
	fill(D, D + N + 1, INT_MAX);
	fill(I, I + N + 1, false);

	// add initial node
	D[1] = 0;
	Q.push(1);

	// put into set
	while (!Q.empty()) {

		// get min
		int s = Q.front();
		Q.pop();
		I[s] = false;

		// iterate neighbors
		for (int i = 0; i < V[s].size(); ++i) {
			if (D[V[s][i]] > D[s] + F[s][i]) {

				D[V[s][i]] = D[s] + F[s][i];
				
				if (!I[V[s][i]]) {
					Q.push(V[s][i]);
					I[V[s][i]] = true;
				}

			}
		}

	}

	// write dists
	for (i = 2; i <= N; ++i) {
		fout << (D[i] == INT_MAX? 0: D[i]) << ' ';
	}

	fout << '\n';
	
	fin.close();
	fout.close();

	return 0;

}