#include <iostream>
#include <set>
#include <vector>
#include <fstream>
#define nmax 50005
#define value first
#define node second
#define inf (1<<28)
using namespace std;

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

vector< pair<int, int> > v[nmax];
set< pair<int, int> > s;

int n, m;
int best[nmax];

void get_data(){
	int x, y, w;
	fin >> n >> m;
	for(int i=1; i<=m; i++){
		fin >> x >> y >> w;
		v[x].push_back(make_pair(w, y));

	}
}

void dijkstra(){
    fin.sync_with_stdio(false);
	for(int i=2; i<=n; i++)		best[i]= inf;				 // set the distances to infinity
	s.insert(make_pair(0, 1));                          //insert the first node and it's value
	while(!s.empty()){  								// while the set have elements
		int current= s.begin()-> node;		             // current node
		int current_val= s.begin() -> value	; 					// current node's value
		s.erase(s.begin());										 // erase thr pair that was just memorized
		for(int i=0; i<v[current].size(); i++){ 						// iterate the neighs of the current node
			int neigh= v[current][i].node; 							// the neight
			int neigh_value= v[current][i].value; 							// the niegh's value
			if(best[neigh] > best[current] + neigh_value){
				best[neigh]= best[current] + neigh_value; // upgrade the new best
				s.insert(make_pair(best[neigh], neigh)); // form a new pair with the new best and the new best's val
			}
		}
	}
	for(int i=2; i<=n; i++){
		if(best[i]==inf)	fout << 0 << " ";
	else fout << best[i] << " ";
    }
}

int main() {
	fin.sync_with_stdio(false);
	get_data();
	dijkstra();
	return 0;
}