#include <fstream>
#include <iostream>
#include <vector>
#include <map>
#include <queue>

const int MAX = 2001;

using namespace std;

template <class T> struct greater2 : binary_function <T, T, bool> {
    bool operator() (const T& x, const T& y) const {
        return x.second > y.second;
    }
};


int main(){
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	int n, m, i;
	f>>n>>m;
	map<int, vector< pair<int, int> > > outbound;
	map<int, int> distances;
	map<int, bool> visited;
	
	for (i = 1; i <= n; i++){
		distances[i] = MAX;
		visited[i] = false;
	}
	
	for (i = 0; i < m; i++){
		int a, b, c;
		f>>a>>b>>c;
		outbound[a].push_back(make_pair(b, c)); 
	}
	f.close();
	
	
	priority_queue< pair<int, int>, vector< pair<int, int> >, greater2< pair<int, int> >  > qu;
	qu.push( make_pair(1, 0) );
	distances[1] = 0;
	
	pair <int, int> c;
	
	while (! qu.empty() ){
		c = qu.top();
		//cout<<"Expanding "<<c.first<<endl;
		qu.pop();		
		visited[ c.first ] = true;
		
		vector< pair<int, int> > v = outbound[c.first];
		for ( vector< pair<int, int> >::iterator it = v.begin(); it != v.end(); ++it){
			pair<int, int> p = *it;
			if (visited[p.first]) continue;
			if ( c.second + p.second < distances[p.first] ){
				distances[p.first] = c.second + p.second;
				qu.push( make_pair(p.first, distances[p.first] ) ); 
			}
		}
		/*
		for (i = 2; i <= n; i++){
				cout<<i<<":"<<distances[i]<<" ";
		}
		cout<<endl;
		*/
	}
	
	
	//return 0;
	for (i = 2; i <= n; i++)
		if (distances[i] == MAX ) g<<"0 ";
		else g<<distances[i]<<" ";
	g.close();
	
	return 0;
}