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

using namespace std;

const int N = 5e4 + 1, INF = 1 << 30;

struct p {
	int cost;
	int nod;
};

struct cmp {
	bool operator()(const p& P1, const p& P2) {
		return P1.cost > P2.cost;
	}
};

vector<p> gr[N];
int n, dist[N];
bool viz[N];

void dijkstra(int src) {
	dist[src] = 0;
	for (int i = 1; i <= n; ++i)
		if (i != src)
			dist[i] = INF;
	priority_queue<p, vector<p>, cmp> pq;
	pq.push({ 0, src });

	int nod;
	while (!pq.empty()) {
		nod = pq.top().nod;
		pq.pop();
		if (!viz[nod]) {
			viz[nod] = true;
			for (auto i : gr[nod])
				if (!viz[i.nod] && i.cost + dist[nod] < dist[i.nod]) {
					dist[i.nod] = i.cost + dist[nod];
					pq.push({ dist[i.nod], i.nod });
				}
		}
	}
}

int main() {
	ifstream in("dijkstra.in");
	ofstream out("dijkstra.out");

	int m, x, y, c;
	in >> n >> m;
	while (m--) {
		in >> x >> y >> c;
		gr[x].push_back({ c, y });
	}
	dijkstra(1);
	for (int i = 2; i <= n; ++i)
		out << dist[i] << ' ';

	in.close();
	out.close();
}