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

using namespace std;

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

#define MAX 987654321

int d[50010];

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() {
		set<ii> q;
		for (int i = 0; i < 5002; ++i) {
			d[i] = MAX;
		}
		q.insert(make_pair(1, 0));
		d[1] = 0;
		while (!q.empty()) {
			auto it = q.begin();
			int node = it->first;
			
			q.erase(it);
			
			for (auto vecin : _g[node]) {
				int iv = vecin.first;
				int ival = vecin.second;
				int dist = d[node] + ival;

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

					d[iv] = dist;
					q.insert(make_pair(iv, dist));
				}
			}
		}
	}

	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;

}