#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){
		//if(x==0 || y==0) return false;
		int i = 0, j = 0;
		for(i = 0; i < tpl[1].vecini.size(); ++i){
		 	if(tpl[1].vecini[i].nod == x) {
		 		printf("x=%d\n", x);
		 		break;
		 	}
		}
		for(j = 0; j < tpl[1].vecini.size(); ++j){
		 	if(tpl[1].vecini[j].nod == y){
		 		printf("y=%d\n", y);
		 		break;
		 	} 
		}
		
		return tpl[1].vecini[i].c > tpl[1].vecini[j].c;
		//return true;
	}
};



void Dijkstra(){

	tpl[1].in_heap = true;

	
	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(unsigned int i = 0; i < tpl[u].vecini.size(); ++i){
			int v = tpl[u].vecini[i].nod;

			if(tpl[v].in_heap == false && tpl[v].d > tpl[u].d + tpl[u].vecini[i].c){
				tpl[v].d = tpl[u].d + tpl[u].vecini[i].c;
				minHeap.push_back(v);
				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;
	
	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 = 1001;
	}

	Dijkstra();

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