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

using muchie = pair<int, long long>;
using comanda = muchie;

using graf = vector<vector<muchie> >;

void citeste_graf(ifstream& f, graf& g){
	int n, m;
	f >> n >> m;
	g.resize(n);
	for(int i = 0, a, b, c; i < m; ++i){
		f >> a >> b >> c;
		g[a-1].emplace_back(b-1, c); } }

void dijkstra(const graf& g, const int st, vector<long long>& dist){

	dist[st] = 0;
	auto comanda_cmp = [](const comanda& lhs , const comanda& rhs){
		return lhs.second > rhs.second; };
	priority_queue<comanda, vector<comanda>, decltype(comanda_cmp)> de_viz(
		comanda_cmp);
	de_viz.emplace(st, 0);
	while(!de_viz.empty()){
		const long long cur = de_viz.top().first, dist_cur = de_viz.top().second;
		de_viz.pop();
		if(dist[cur] == dist_cur){
			for(const auto next : g[cur]){
				if(dist[next.first] > dist_cur + next.second){
					dist[next.first] = dist_cur + next.second;
					de_viz.emplace(next.first, dist[next.first]); } } } } }

int main(){
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	graf gr;
	citeste_graf(f, gr);
	vector<long long> dist(gr.size(), 60000000);
	dijkstra(gr, 0, dist);
	for(int i = 1; i < gr.size(); ++i){
		g << (dist[i] == 60000000 ? 0 : dist[i]) << ' '; }
	return 0; }