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

using namespace std;

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

#define maxx 50003
#define inf 0x3f3f3f3f

int n, m;
int dist[maxx];
bool inQueue[maxx];
vector<pair<int, int>> adj[maxx];

class Compare {
public:
	bool operator() (int x, int y) {
		return dist[x] > dist[y];
	}
};

priority_queue<int, vector<int>, Compare> q;

void read() {
	fin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int x, y, cost;
		fin >> x >> y >> cost;
		adj[x].push_back(make_pair(y, cost));
	}
}

void dijkstra(int startNode) {
	for (int i = 1; i <= n; ++i) {
		dist[i] = inf;
	}
	dist[startNode] = 0;
	q.push(startNode);
	inQueue[startNode] = true;
	while (!q.empty()) {
		int currNode = q.top();
		q.pop();
		inQueue[currNode] = false;
		vector<pair<int, int>> neighbors = adj[currNode];
		for (pair<int, int> neighbor: neighbors) {
			if (dist[currNode] + neighbor.second < dist[neighbor.first]) {
				dist[neighbor.first] = dist[currNode] + neighbor.second;
				if (!inQueue[neighbor.first]) {
					inQueue[neighbor.first] = true;
					q.push(neighbor.first);
				}
			}
		}
	}
}

void print() {
	for (int i = 2; i <= n; ++i) {
		if (dist[i] != inf) {
			fout << dist[i] << ' ';
		} else {
			fout << "0 ";
		}
	}
}

int main() {
	read();
	dijkstra(1);
	print();
	return 0;
}