#include <queue>
#include <fstream>
#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 = MAXVAL * MAXN;

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;
int n, m;
vector <tip>g[MAXN + 1];
int d[MAXN + 1];

void dijkstra(tip start) {
	pq.push(start);

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

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

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

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

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

	return 0;
}