#include <iostream>
#include <fstream>
#include <vector>
#include <set>

const int INF = 1<<29;
const int NMAX = 5e4  + 5;

using namespace std;

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

vector < pair < int, int > > g[NMAX];
set < pair <int, int > > heap;

int d[NMAX];

int n, m;

int main(){
	fin >> n >> m;
	while(m--){
		int a, b, c;
		fin >> a >> b >> c;
		g[a].push_back({b, c});
	}
	for(int i = 2; i <= n; i++)
		d[i] = INF;
	heap.insert({1, 0});
	while(!heap.empty()){
		auto h = *heap.begin();
		int nod = h.first;
		heap.erase(heap.begin());
		for(auto i : g[nod]){
			if(d[i.first] > d[nod] + i.second){
				if(d[i.first] != INF)
					heap.erase(heap.find({i.first, d[i.first]}));
				d[i.first] = d[nod] + i.second;
				heap.insert({i.first, d[i.first]});
			}
		}
	}
	for(int i = 2; i <= n; i++)
		if(d[i] == INF)
			fout << "0 ";
		else
			fout << d[i] << ' ';
	return 0;
}