#include <list>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

class Comparator {
	public:
		Comparator(vector<int>* A) { 
			this -> A = A;
		}
		bool operator()(int a, int b) {
			return (*A)[a] < (*A)[b];
		}
	private:
		vector<int>* A;
};

class Graph {
	public:
		Graph(int N) {
			this->N = N;
			edges.resize(N);
		}

		void add_edge(int x, int y, int c) {
			edges[x].push_back(make_pair(y, c));
		}

		vector<int> dijkstra(int start) {
			vector<int> distances(N);
			fill(distances.begin(), distances.end(), 0x7fffffff);
			distances[start] = 0;

			vector<bool> enq(N);
			fill(enq.begin(), enq.end(), false);

			Comparator comp(&distances);
			priority_queue<int, vector<int>, Comparator> Q(comp);
			Q.push(start);
			enq[start] = true;
			while (! Q.empty()) {
				int x = Q.top();
				Q.pop();
				for (list<pair<int, int> >::iterator it=edges[x].begin();
						it != edges[x].end();
						++it) {
					if (distances[it->first] > distances[x] + it->second) {
						distances[it->first] = distances[x] + it->second;
						if (!enq[it->first]) {
							Q.push(it->first);
						}
					}
				}
			}

			return distances;
		}

	private:
		int N;
		vector< list<pair<int, int> > > edges;
};

int main() {
	ifstream in("dijkstra.in");
	ofstream out("dijkstra.out");

	int N, M;
	in >> N >> M;
	Graph G(N);
	while (M --) {
		int x, y, c;
		in >> x >> y >> c;
		G.add_edge(x-1, y-1, c);
	}

	vector<int> distances = G.dijkstra(0);
	for (int i=1; i<N; ++i)
		out << distances[i] << " ";
	out << "\n";
	return 0;
}