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


#define INF 1 << 30

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(){

	push_heap(minHeap.begin(), minHeap.end(), comparator());


	while(!minHeap.empty()){

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

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


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

 			if(tpl[v].d > tpl[u].d + tpl[u].vecini[i].c){

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




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;
	 		minHeap.push_back(y);
	 	}
	 	else tpl[y].d = INF;
	}


	Dijkstra();

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