#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <iterator>
#include <functional>


using namespace std;


struct cost{
	int nod;
	int c;
};

struct info{
	vector<cost> vecini;
	int d;
	bool in_heap;
};




int N, M;

vector <int> minHeap;
vector<info>tpl;



struct comparator{
	bool operator()(int x, int y){
		return tpl[x].d > tpl[y].d;
		
	}
};





void Dijkstra(){

	while(!minHeap.empty()){
		
		push_heap(minHeap.begin(), minHeap.end(), comparator());

		int u = minHeap.front();
		tpl[u].in_heap = false;

		pop_heap(minHeap.begin(), minHeap.end(), comparator());
		minHeap.pop_back();

		for(unsigned int i = 0; i < tpl[u].vecini.size(); ++i){
			int v = tpl[u].vecini[i].nod;

			if(tpl[v].in_heap == true && tpl[v].d > tpl[u].d + tpl[u].vecini[i].c){
				tpl[v].d = tpl[u].d + tpl[u].vecini[i].c;
				//push_heap(minHeap.begin(), minHeap.end(), comparator());
				
			}
		}
	}
}


int main(){

	freopen("dijkstra.in", "rt", stdin);
	freopen("dijkstra.out", "wt", stdout);

	cin >> N >> M;

	int x, y, c;



	tpl.resize(N+1);

	tpl[1].d = 0;
	
	tpl[1].in_heap = true;


	for(int i = 0; i < M; ++i){
	 	cin >> x >> y >> c;
	 	cost v;
	 	v.nod = y;
	 	v.c = c;
	 	tpl[x].vecini.push_back(v);
	 	
	 	if(x == 1) {
	 		tpl[y].d = c;
	 	}
	 	else tpl[y].d = 1001;
	}

	for(int i = 2; i <= N; ++i){
		minHeap.push_back(i);
		tpl[i].in_heap = true;
	}

	Dijkstra();

	for(int i = 2; i < N+1; ++i){
		if(tpl[i].d == 1001) 
			cout << 0 << " ";
		else cout << tpl[i].d << " ";
	}
}