#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <fstream>
#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;


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


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


void read(){

	in >> N >> M;

	int x, y, c;

	tpl.resize(N+1);
	tpl[1].d = 0;

	for(int i = 0; i < N+1; ++i){
		tpl[i].d = INF;
		tpl[i].in_heap = false;
	}


	tpl[1].in_heap = true;

	for(int i = 0; i < M; ++i){
	 	in >> 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);
	 		tpl[y].in_heap = true;
	 	}
	}
}


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;
 			int dist = tpl[u].d + tpl[u].vecini[i].c;

 			if(tpl[v].in_heap == false){
 				tpl[v].d = dist;
 				minHeap.push_back(v);
 				push_heap(minHeap.begin(), minHeap.end(), comparator());
 	 			tpl[v].in_heap = true;
 			}

 			else{
 				if(tpl[v].d > dist){
	 				tpl[v].d = dist;
	 				push_heap(minHeap.begin(), minHeap.end(), comparator());
 				}
 			}
 		}
	}
}




int main(){

	read();

	Dijkstra();

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