#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
#include <string.h>

#define NMax 100010
#define INF 0x7ffff

using namespace std;


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


class Nod {

public:
	int index, dist; //indexul nodului, distanta de la sursa la nod
	std::vector<int> adiacent;
	std::vector<int> cost;


	
};


class Pair {

public:
	int index;
	int dist;
	
	bool operator > (const Pair &n) {
		return dist > n.dist;
	}

};


class PQueue {
	
public:
	std::vector<Pair> heap; //heap-ul propriu-zis
	std::vector<int> poz; //pozitia in heap a nodului i


	PQueue (std::vector<Nod> &v, int N) {
		poz = vector<int>(N+1);
		heap = vector<Pair>(N+1);

		for (size_t i = 1; i <= N; i++) {
			heap[i].index = v[i].index;
			heap[i].dist = v[i].dist;
	
			poz[v[i].index] = i;	
		}
	}

	void sieve(int father) {

		int left_son = 2 * father;
		int right_son = 2 * father + 1;

		int minim = father;
		if (left_son < heap.size() && heap[minim] > heap[left_son]) {
			minim = left_son;
		}

		if (right_son < heap.size() && heap[minim] > heap[right_son]) {
			minim = right_son;
		}

		if (minim != father) {
			swap(poz[heap[father].index], poz[heap[minim].index]);
			swap(heap[father], heap[minim]);
			sieve(minim);		
		}
		

	}

	void up_sieve(int position) {
		int father = position >> 1;
		if (father == 0) // daca am ajuns in radacina 
			return;

		if (heap[father] > heap[position]) {
			swap(poz[heap[father].index], poz[heap[position].index]);
			swap(heap[position], heap[father]);
			up_sieve(father);
		}
	}

	
	void build_heap() {
		
		for (int i = heap.size() / 2; i >= 1; i--) {
			sieve(i);
		}
	}	


	Pair& extract_min() {
		return heap[1];
	}

	void pop() {
		//std::cout << heap[1].dist << " ";
		if (!is_empty()) {
			swap(poz[heap[1].index], poz[heap[heap.size()-1].index]);
			swap(heap[1], heap[heap.size() - 1]);

			heap.pop_back();
		
			sieve(1);
		}
	}


	bool is_empty() {
		return heap.size() == 1;
	}
	
};


int get_cost(int n1, int n2, std::vector<Nod> graf) {
	for (size_t i = 0; i < graf[n1].adiacent.size(); i++)
		if (graf[n1].adiacent[i] == n2) {
			return graf[n1].cost[i];
		} 

	return INF;
}

void solve(int sursa, int N, std::vector<Nod> graf) {
	
	bool viz[N+1];
	memset(viz, false, sizeof(viz));
		

	for (int i = 1; i <= N; i++) {
		if (i == sursa) graf[i].dist = 0;
		else graf[i].dist = INF;
	}
	
	PQueue queue(graf, N);
	queue.build_heap();
	
	
	while (!queue.is_empty()) {
		Pair n = queue.extract_min();
		graf[n.index].dist = n.dist;
		queue.pop();
	
		for (size_t i = 0; i < graf[n.index].adiacent.size(); i++) {
			int lung = graf[n.index].cost[i];
			if (queue.heap[queue.poz[graf[n.index].adiacent[i]]].dist > n.dist + lung ) {
				queue.heap[queue.poz[graf[n.index].adiacent[i]]].dist = n.dist + lung;
				queue.up_sieve(queue.poz[graf[n.index].adiacent[i]]);
			}
		}
	
	}	

	for (int i = 1; i <= N; i++) {
		if (i != sursa) {
			if (graf[i].dist != INF) fout << graf[i].dist << " ";
			else fout << 0 << " ";
		}
	}

	fout << '\n';
	
}



int main() {


	int N, M;
	fin >> N >> M;

	std::vector<Nod> graf(N+1);
	for(int i = 1; i <= N; i++)
		graf[i].index = i;	

	for (int i = 1; i <= M; i++) {
		int x, y, cost;
		
		fin >> x >> y >> cost;
		graf[x].adiacent.push_back(y);
		graf[x].cost.push_back(cost);		
	
	} 
   
	int sursa = 1;
	solve(sursa ,N, graf);

    return 0;
}