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

#define INF 1<<30

using namespace std;

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


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



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

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);

	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;
			minHeap.push_back(y);
			in_heap[y] = true;
		}
	}

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


void Dijkstra(){

	make_heap(minHeap.begin(), minHeap.end(), comparator());

	while(!minHeap.empty()){

		int u = minHeap.front();
		in_heap[u] = true;

		pop_heap(minHeap.begin(), minHeap.end(), comparator());
		minHeap.pop_back();

		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;
				minHeap.push_back(v);
				push_heap(minHeap.begin(), minHeap.end(), comparator());
				in_heap[v] = true;
			}

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


int main(){

	read();
	Dijkstra();

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

}