#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <fstream>
#include <utility>
#include <queue>
#include <functional>

using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;

#define MAX 987654321
#define NMAX 50010

int d[NMAX];



class Graph {
public:
	
	Graph(string f) {
		ifstream iff(f);
		iff >> N >> M;
		_g = vvii(N + 1, vii());

		for (int i = 0; i < M; ++i) {
			int A, B, C;
			iff >> A >> B >> C;
			_g[A].push_back(make_pair(B, C));
		}
	}

	void dijkstra() {
		priority_queue<ii, vii, greater<ii>> q;
		for (int i = 0; i < NMAX; ++i) {
			d[i] = MAX;
		}
		q.emplace(make_pair(0, 1));
		d[1] = 0;
		while (!q.empty()) {
			auto it = q.top();
			int node = it.second;
			
			q.pop();
			
			for (auto vecin : _g[node]) {
				int iv = vecin.first;
				int ival = vecin.second;

				int dist = d[node] + ival;

				if (d[iv] > dist) {
					d[iv] = dist;
					q.push(make_pair(dist, iv));
				}
			}
		}
	}

	int N;

private:
	vector<vii> _g;
	int M;
};



int main() {
	Graph g("dijkstra.in");
	ofstream off("dijkstra.out");

	 g.dijkstra();
	for (int i = 2; i <= g.N; ++i) {
		if (d[i] == MAX) {
			off << 0 << " ";
		}
		else {
			off << d[i] << " ";
		}
	}
	off << endl;

}