#include <stdio.h>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iterator>

#define INF 1<<30

using namespace std;

struct Heap{
	int size = 0;
	vector< pair<int,int> > vecini;
	vector<int> indx;

};


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


int N, M;
vector< vector< pair<int,int> > > neigh;
vector<int> d;
vector<bool> in_heap;
Heap minHeap;


void exch(int i, int k){

	minHeap.indx[(minHeap.vecini[i]).first] = k;
	minHeap.indx[minHeap.vecini[k].first] = i;

	pair<int,int> tmp = minHeap.vecini[i];
	minHeap.vecini[i] = minHeap.vecini[k];
	minHeap.vecini[k] = tmp;
}

void PUSH(pair<int,int> p){
	int i = minHeap.size;
	minHeap.vecini[i] = p;
	minHeap.indx[p.first] = i;

	while(i >= 0 && minHeap.vecini[i].second < minHeap.vecini[(i-1)/2].second){
		int k = (i-1)/2;
		exch(i,k);
		i = k;
	}

	++(minHeap.size);
}


void POP(){

	--(minHeap.size);
	minHeap.vecini[0] = minHeap.vecini[minHeap.size];

	int i = 0, ok = 0;
	while(!ok){
		int l = 2*i+1;
		int r = 2*i+2;
		if(r < minHeap.size && (minHeap.vecini[i].second > minHeap.vecini[l].second || minHeap.vecini[i].second > minHeap.vecini[r].second)){
			if(minHeap.vecini[l].second < minHeap.vecini[r].second){
				exch(i,l);
				i = l;
			}
			else{
				exch(i,r);
				i = r;
			}
		}
		else if(l < minHeap.size && minHeap.vecini[i].second > minHeap.vecini[l].second){
			exch(i,l);
			i = l;
		}
		else ok = 1;
	}
}


void SORT(int index, int dist){

	int i = minHeap.indx[index];
	minHeap.vecini[i].second = dist;

	while(i >= 0 && minHeap.vecini[i].second < minHeap.vecini[(i-1)/2].second){
		int k = (i-1)/2;
		exch(i,k);
		i = k;
	}	
}

void read(){

	in >> N >> M;

	d.resize(N+1);
	d.assign(N+1, INF);

	in_heap.resize(N+1);
	in_heap.assign(N+1,false);

	minHeap.vecini.resize(N+1);
	minHeap.indx.resize(N+1);

	for(int i = 0; i <= N; ++i){
		vector< pair<int,int> > v;
		neigh.push_back(v);
	}

	int x, y, c;

	for(int i = 0; i < M; ++i){
		in >> x >> y >> c;
		neigh[x].push_back(make_pair(y,c));
		if(x == 1){
			d[y] = c;
			PUSH(make_pair(y,c));
			in_heap[y] = true;
		}
	}

	d[1] = 0;
	in_heap[1] = true;
}


void Dijkstra(){

	while(minHeap.size){

		int u = minHeap.vecini[0].first;

		POP();

		for(int i = 0; i < neigh[u].size(); ++i){
			int v = neigh[u][i].first;
			int dist = d[u] + neigh[u][i].second;

			if(in_heap[v] == false){
				d[v] = dist;
				PUSH(neigh[u][i]);
				in_heap[v] = true;
			}

			else{
				if(d[v] > dist){
					d[v] = dist;
					SORT(v, dist);
				}
			}
		}
	}
}


int main(){

	read();
	Dijkstra();

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

}