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

#define nm 50001

using namespace std;

vector< pair<int, int> > W[nm];
queue<int> Q;
int N;

int main() {

	int x, y, l, M, i;
	vector< pair<int, int> >::iterator t;
	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;
		W[x].push_back(pair<int, int>(y, 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 (t = W[s].begin(); t != W[s].end(); ++t) {
			x = t->first;
			y = t->second;

			if (D[x] > D[s] + y) {

				D[x] = D[s] + y;
				
				//if (!I[x]) {
					Q.push(x);
					//I[x] = 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;

}