#include <bits/stdc++.h>
#define inf INT_MAX

using namespace std;

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

int n, m, d[250001] = {inf};
vector<pair<int, int>> adj[250001];
set<pair<int, int>> s;

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

void dijkstra(){
	int c1, c2;
	for(int i = 1; i <= n; i++)
		d[i] = inf;
	d[1] = 0;
	s.insert({1, 0});
	while(!s.empty()){
		int u, v;
		u = s.begin()->first;
		c1 = s.begin()->second;
		s.erase(s.begin());
		for(pair<int, int> i : adj[u]){
			v = i.first;
			c2 = i.second;
			if(d[v] > d[u] + c2){
				if(d[v] != inf)
					s.erase(s.find({v, d[v]}));
				d[v] = d[u] + c2;
				s.insert({v, d[v]});
			}
		}
	}
	for(int i = 2; i <= n; i++)
		fout << (d[i] != inf ? d[i] : 0) << " ";
}

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