#include <fstream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

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

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

vector<pair<int, int> > g[MAXN + 1];
int d[MAXN + 1];
int n, m;

class cmp {
public:
	bool operator() (pair<int, int> a, pair<int, int> b) {
		if (a.second <= b.second) return false;
		else return true;
	}
};

void dijkstra(int start) {
	d[start] = 0;
	pair<int, int> cur = {start, 0};
	priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> pq;
	pq.push(cur);

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

		if (d[cur.first] != cur.second)
			continue;
		for (auto x : g[cur.first]) {
			if (cur.second + x.second < d[x.first]) {
				d[x.first] = cur.second + x.second;
				pq.push({x.first, d[x.first]});
			}
		}
	}
}

int main() {
	memset(d, 0x3f3f3f3f, sizeof(d));
	in >> n >> m;
	for (int i = 1; i <= m; ++ i) {
		int x, y, z;
		in >> x >> y >> z;
		g[x].push_back({y, z});
	}

	dijkstra(1);

	for (int i = 1; i <= n; ++ i) out << d[i] << ' ';

	return 0;
}