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

const int MAX = 1000000;

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;
	vector< pair<int, pair<int, int> > > edges;
	map<int, int> distances;
		
	for (i = 0; i < m; i++){
		int a, b, c;
		f>>a>>b>>c;
		edges.push_back(make_pair(a, make_pair(b, c))); 
	}
	f.close();
	
	for (i = 1; i <= n; i++){
		distances[i] = MAX;
	}
	distances[1] = 0;

	for (i = 1; i < n - 1; i++){
		for (vector<pair<int, pair<int,int> > >::iterator iter = edges.begin(); iter != edges.end(); ++iter){
			//cout<<iter->first<<" "<<iter->second.first;
			int u = iter->first;
			int v = iter->second.first;
			int w = iter->second.second;
			//cout<<u<<" "<<v<<" "<<w<<endl;
			if ( distances[u] + w < distances[v] ) distances[v] = distances[u] + w;
		}
	}
	
	/*
	for (map<int, pair<int, int> >::iterator iter = edges.begin(); iter != edges.end(); ++iter){
			int u = iter->first;
			int v = iter->second.first;
			int w = iter->second.second;
			if ( distances[u] + w < distances[v] ) cout<<"Negative cycle";
	}
	*/
	
	for (i = 2; i <= n; i++)
		if (distances[i] == MAX ) g<<"0 ";
		else g<<distances[i]<<" ";
	g.close();
	
	return 0;
}