#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int MAXN = 5e4;
const int MAXM = 25e4;
const int MAXVAL = 2e4;
const int INF = MAXN * MAXVAL;

struct tip {
	int dist;
	int nod;

	tip(int _dist = INF, int _nod = 0) {
		dist = _dist; nod = _nod;
	}
};

class cmp {
	public :
		bool operator() (const tip a, const tip b) const{
			return a.dist > b.dist;
		}
};

priority_queue <tip, vector <tip>, cmp>pq;
vector <tip>g[MAXN + 1];
int n, m;
int d[MAXN + 1];

void dijkstra(int start) {
	d[start] = 0;

	tip cur;
	cur.dist = 0;
	cur.nod = start;
	pq.push(cur);

	while (pq.size()) {
		cur = pq.top();
		pq.pop();

		if (d[cur.nod] != cur.dist)
			continue;
		for (auto x : g[cur.nod]) {
			if (d[x.nod] > cur.dist + x.dist) {
				tip p;
				p.nod = x.nod;
				p.dist = cur.dist + x.dist;
				d[p.nod] = p.dist;
				pq.push(p);
			}
		}
	}
}

int main() {
	in >> n >> m;

	int a, b, c;
	tip p;
	for (int i = 1; i <= m; ++ i) {
		in >> a >> b >> c;
		p.nod = b;
		p.dist = c;
		g[a].push_back(p);
	}

	for (int i = 2; i <= n; ++ i)
		d[i] = INF;

	dijkstra(1);

	for (int i = 2; i <= n; ++ i) {
		if (d[i] == INF)
			out << 0 << ' ';
		else
			out << d[i] << ' ';
	}

	return 0;
}