#include <iostream>
#include <vector>
#include <climits>
#include <set>
#include <cstdlib>

#define NMAX 50005

#define SWAP(a, b){\
    a = a + b;\
    b = a - b;\
    a = a - b;\
}

struct neigh{
	int id, dist;
};

typedef struct neigh neigh;

using namespace std;

int N, M, H;
vector<neigh> neigh_list[NMAX];  
int optim_dist[NMAX], current_dist[NMAX], Heap[NMAX], Pos[NMAX];

inline int getLeft(int n){ return 2 * n;}
inline int getRight(int n){ return 2 * n + 1;}
inline int getParent(int n){ return n / 2;}

void up(int p){
	while(p > 1 && current_dist[Heap[p]] < current_dist[Heap[getParent(p)]]){
		SWAP(Heap[p], Heap[getParent(p)]);
		Pos[Heap[p]] = p;
		Pos[Heap[getParent(p)]] = getParent(p);
		p = getParent(p);
	}	
}

void down(int p){
	int son;
	do{
		son = 0;
		if(getLeft(p) <= H){
			son = getLeft(p);
			if(getRight(p) <= H && current_dist[Heap[son]] > current_dist[Heap[getRight(p)]])
				son = getRight(p);
		}
		if(son){
			if(current_dist[Heap[p]] > current_dist[Heap[son]]){
				SWAP(Heap[p], Heap[son]);
				Pos[Heap[p]] = p;
				Pos[Heap[son]] = son;
				p = son;
			}
			else
				son = 0;
		}
	}while(son);
}

void cutMin(){
	int pos = 1;
	if(pos != H){
		Heap[pos] = Heap[H--];
		Pos[Heap[pos]] = pos;
		
		if(H > 1)
			down(pos);
	}
	else
		--H;
}

int main(){
	freopen("dijkstra.in",  "rt", stdin);
	freopen("dijkstra.out", "wt", stdout);
	
	cin >> N >> M;
	H = N;
	
	for(int i = 0; i < M; ++i){
		int A, B, C;
		cin >> A >> B >> C;
		neigh n;
		n.id = B;
		n.dist = C;
		neigh_list[A].push_back(n);
	}
	
	current_dist[1] = 0;
	for(int i = 2; i <= N; ++i)
		current_dist[i] = INT_MAX;
	for(int i = 1; i <= N; ++i)
		Heap[i] = Pos[i] = i;
		
	set<int> processed;
	// while the heap is not empty	
	while(H > 0){
		int p = Heap[1];
		optim_dist[p] = current_dist[p];
		processed.insert(p);
		cutMin();
		for(unsigned i = 0; i < neigh_list[p].size(); ++i)
			if(processed.find(neigh_list[p][i].id) == processed.end()){
				if(current_dist[neigh_list[p][i].id] > current_dist[p] + neigh_list[p][i].dist){
					current_dist[neigh_list[p][i].id] = current_dist[p] + neigh_list[p][i].dist;
					up(Pos[neigh_list[p][i].id]);
				}
			}
	}
		
	for(int i = 2; i <= N; ++i)
		cout << optim_dist[i] << " ";
	
	return 0;
}