#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <vector>
#include <iterator>
#include <functional>

#define MAX 250000

using namespace std;



int N, M;

vector <int> neigh[100];
int** top;
vector <int> d;
vector <bool> in_heap;
vector <int> minHeap;



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


void Dijkstra(){

	in_heap[1] = true;

	
	push_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(unsigned int i = 0; i < neigh[u].size(); ++i){
			int v = neigh[u][i];

			if(in_heap[v] == false && d[v] > d[u] + top[u][v]){
				d[v] = d[u] + top[u][v];
				minHeap.push_back(v);
				push_heap(minHeap.begin(), minHeap.end(), comparator());
			}
		}
	}
}


int main(){

	freopen("dijkstra.in", "rt", stdin);
	freopen("dijkstra.out", "wt", stdout);

	cin >> N >> M;

	int x, y, c;

	top = new int*[N+1];

	for(int i = 0; i < N+1; ++i){
	   	top[i] = new int[N+1];

	}

	for(int i = 0; i < N+1; ++i)
		for(int j = 0; j < N+1; ++j)
	   	top[i][j] = 0;

	

	d.resize(N+1);
	d.assign(N+1,1001);
	d[1] = 0;


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




	
	for(int i = 0; i < M; ++i){
	 	cin >> x >> y >> c;
	 	top[x][y] = c;
	 	neigh[x].push_back(y);
	 	if(x == 1) {
	 		d[y] = c;
	 		minHeap.push_back(y);
	 	}
	}

	Dijkstra();

	for(int i = 2; i < N+1; ++i){
		if(d[i] == 1001) d[i] = 0;
		cout << d[i] << " ";
	}
	//cout << "\n";
}