#include <iostream>
#include <vector>
#include <utility>
#include <climits>
#define MAX  50009
#define MAXIM 200009

using namespace std;

int N;

class Item {
public:
	int cost, nod;
	Item(int nod, int cost) : cost(cost), nod(nod) {}
	Item() {}
};


vector<vector<pair<int,int>>> adj(MAX);	// <node_from, <node_to, cost>>
vector<int> distances(MAX, INT_MAX);
vector<Item> H(MAXIM);	// the node and the position in posHeap
vector<int> posHeap(MAXIM, 0);

int father(int node){
	return node/2;
}

int left_son(int node){
	return 2*node;
}

int right_son(int node){
	return node*2+1;
}

void sift(int index){
	int son;
    do {
        son = 0;
        if (left_son(index) < N) {
            son = left_son(index);
            if (right_son(index) < N && H[right_son(index)].cost < H[left_son(index)].cost) {
                son = right_son(index);
            }
            if (H[son].cost >= H[index].cost) {
                son = 0;
            }
        }
  
        if (son) {
            posHeap[H[index].nod] = son;
			posHeap[H[son].nod] = index;
			swap(H[index], H[son]);
            index = son;
        }
    } while (son);
}

void percolate(int index){
	int f, cost = H[index].cost, nod = H[index].nod;
	while(index > 1 && cost < H[f = father(index)].cost){
		H[index] = H[f];
		posHeap[H[f].nod] = index;
		index = f;
	}
	H[index] = Item(nod, cost);
	posHeap[nod] = index;
}

void insertH(int nod, int cost){
	H[N] = Item(nod, cost);
	posHeap[nod] = N;
	percolate(N);
	N++;
}

void extractMinH(){
	int index = 1;
	H[index] = H[N-1];
	posHeap[H[index].nod] = -1;
	posHeap[H[N-1].nod] = index;
	N--;
	sift(index);
}

void modifyH(int nod, int cost){
	int index = posHeap[nod], f;
	H[index].cost = cost;
	if(index > 1 && H[index].cost < H[f = father(index)].cost){
		percolate(index);
	}else{
		sift(index);
	}
}

void dijkstra(){

	Item p;
	pair<int, int> r;
	while(N > 1){
		p = H[1];
		extractMinH();
		for(int i = 0; i < adj[p.nod].size(); i++){
			r = adj[p.nod][i];
			if(posHeap[r.first] != -1 && distances[r.first] > distances[p.nod] + r.second){
				distances[r.first] = distances[p.nod] + r.second;
				modifyH(r.first, distances[r.first]);
			}
		}
	}
}


int main(){
	freopen("dijkstra.in", "r", stdin);
	freopen("dijkstra.out", "w", stdout);
	int n, m, a, b, cost;
	scanf("%d%d", &n, &m);
	N = 1;
	for(int i = 0; i < n; i++){
		if(i == 0)
			insertH(i, 0);
		else
			insertH(i, INT_MAX);
	}
	
	distances[0] = 0;

	for(int i = 0; i < m; i++){
		scanf("%d%d%d", &a, &b, &cost);
		adj[--a].push_back(make_pair(--b,cost));
	}

	dijkstra();

	for(int i = 1; i < n; i++){
		if(distances[i] == INT_MAX)
			distances[i] = 0;
		printf("%d ", distances[i]);
	}
	return 0;
}