#include <iostream>
#include <fstream>
#include <queue>
#include <utility>
#include <vector>
#include <algorithm>
#include <limits>
using namespace std;

const int inf = numeric_limits<int>::max();
typedef pair<int, int> int_pair;
typedef vector<int_pair >::iterator int_pair_iterator;
int n;
vector<int_pair > G[50009];
int d[50009];

bool operator > (const int_pair& a, const int_pair& b) {
	return a.second < b.second;
}

void read() {
	ifstream fin("dijkstra.in");
	int m, x, y, c;
	fin >> n >> m;
	for(int i = 1; i <= m; ++i) {
		fin >> x >> y >> c;
		G[x].push_back(make_pair(y, c));
	}
}

void dijkstra() {
	for(int i = 2; i <= n; i++)
		d[i] = inf;

	priority_queue<int_pair> Q;
	Q.push(make_pair(1, 0));

	while(Q.empty() == false) {
		int_pair top = Q.top();
		int vertex = top.first, cost = top.second;
		Q.pop();

		for(int_pair_iterator i = G[vertex].begin(); i != G[vertex].end(); ++i) 
			if(d[i->first] > d[vertex] + i->second) {
				d[i->first] = d[vertex] + i->second;
				Q.push( make_pair(i->first, d[i->first]));
			}
	
	}
}


int main () {

	read();
	dijkstra();
	ofstream fout("dijkstra.out");
	for(int i = 2; i <= n; i++) {
		fout << d[i] << ' ';
	}

	return 0;
}