#include <fstream>
#include <utility>
#include <iostream>
#include <vector>
#include <set>
 #include <climits>

using namespace std;

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

#define N 50005


vector<vector<pair<int, int>>> graphAdj(50005);
set<pair<int, int>> setOfWeight;
vector<int> dist(50005, INT_MAX);
int n, m;

void addEdge(int u, int v, int weight) {

	graphAdj[u].push_back(make_pair(v, weight));
	//graphAdj[v].push_back(make_pair(u, weight));
}

void createGraph() {

	addEdge(0, 1, 4);
	addEdge(0, 7, 8);
	addEdge(1, 2, 8);
	addEdge(1, 7, 11);
	addEdge(2, 3, 7);
	addEdge(2, 8, 2);
	addEdge(2, 5, 4);
	addEdge(3, 4, 9);
	addEdge(3, 5, 14);
	addEdge(4, 5, 10);
	addEdge(5, 6, 2);
	addEdge(6, 7, 1);
	addEdge(6, 8, 6);
	addEdge(7, 8, 7);

}

void initialize(int src) {

	setOfWeight.insert(make_pair(1, src));
	dist[1] = 0;

}

void dijkstra() {

	while (!setOfWeight.empty()) {

		pair<int,int> lowestPair = *(setOfWeight.begin());

		setOfWeight.erase(setOfWeight.begin());

		int weight = lowestPair.first;

		int node = lowestPair.second;


		for (vector<pair<int, int>>::iterator it = graphAdj[node].begin(); it != graphAdj[node].end(); it++) {

			pair<int, int> ditancePair = *(it);
			int toNode = ditancePair.first;
			int toWeight = ditancePair.second;

			if (toWeight + dist[node] < dist[toNode]) {


				if (dist[toNode] != INT_MAX) {

					setOfWeight.erase(setOfWeight.find(make_pair(dist[toNode], toNode)));

				}

				dist[toNode] = toWeight + dist[node];
				setOfWeight.insert(make_pair(dist[toNode], toNode));
			}

		}
	}
}

void read() {

	f >> n >> m;

	int i, u, v, weight;

	for (i = 0; i < m; i++) {

		f >> u >> v >> weight;
		addEdge(u, v, weight);

	}



}

int main()
{
	int src = 1, c;

	read();

	initialize(src);

	dijkstra();

	int i;

	for (i = 2; i <= n; i++) {

		if (dist[i] == INT_MAX) {
			fout << 0 << " ";
		}else
			fout << dist[i] << " ";
	}

    return 0;
}