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

const unsigned int inf = numeric_limits<unsigned int>::max();
typedef pair<unsigned int, unsigned int> uint_pair;
typedef vector<uint_pair>::iterator uint_pair_iterator;
int n;
vector<uint_pair > G[50009];
int d[50009];
bool viz[50009];

bool operator < (const uint_pair& a, const uint_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<uint_pair> Q;
	Q.push(make_pair(1, 0));

	while(Q.empty() == false) {
		uint_pair top = Q.top();
		unsigned int x = top.first;
		Q.pop();
		 
		for(uint_pair_iterator i = G[x].begin(); i != G[x].end(); ++i) {
			unsigned int cost = d[x] + i->second, y = i->first;
			if(d[y] > cost) {
				d[y] = cost;
				Q.push( make_pair(y, cost) );
			}
		}

	}
}


int main () {

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

	return 0;
}