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

#define inf (1 << 30)
#define NMax 50005

using namespace std;

int n, m;

bool inQueue[NMax];
int d[NMax];
vector<pair<int, int> > v[NMax];

struct comparison {
	bool operator() (int x, int y) {
		return d[x] > d[y];
	}
};

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

void read() {	
	ifstream fin("dijkstra.in");
	fin >> n >> m;
	for (int i = 1; i <= n; i++) {
		d[i] = inf;
	}
	int x, y, w;
	for (int i = 0; i < m; i++) {
		fin >> x >> y >> w;
		v[x].push_back(make_pair(y, w));
	}
	fin.close();
}

void solveDijkstra(int node) {
	d[node] = 0;
	q.push(node);
	inQueue[node] = true;

	while (!q.empty()) {
		int current = q.top();
		q.pop();
		inQueue[current] = false;
		for (size_t i = 0; i < v[current].size(); i++) {
			int next = v[current][i].first;
			int cost = v[current][i].second;
			if (d[current] + cost < d[next]) {
				d[next] = d[current] + cost;
				if (inQueue[next] == false) {
					q.push(next);
					inQueue[next] == true;
				}
			}
		}
	}
}

void print() {
	ofstream fout("dijkstra.out");
	for (int i = 2; i <= n; i++) {
		if (d[i] != inf) {
			fout << d[i] << " ";
		} else {
			fout << "0 ";
		}
	}
	fout.close();
}

int main(int argc, char *argv[]) {
	read();
	solveDijkstra(1);
	print();
	return 0;
}