#include <iostream>
#include <vector>

using namespace std;

typedef pair<int, int> pii;
const int MAXN = 1000*100 + 10;
const int INF = 1000*1000*1000;
int dist[MAXN];
vector<pii> edge;
vector<int> w;
int n, m;

void readInput(){
	cin >> n >> m;
	for(int i=0; i<m; ++i){
		int u, v, z;
		cin >> u >> v >> z;
		edge.push_back(pii(u, v));
		w.push_back(z);
	}
}

void bellmanFord(int s)
{
	dist[s] = 0;
	for(int i=0; i<n; ++i)
		if(i!=s)
			dist[i] = INF;
	for(int i=0; i<n-1; ++i)
		for(int j=0; j<(int)edge.size(); ++j){
			int u = edge[j].first;
			int v = edge[j].second;
			dist[v] = min(dist[v], dist[u]+w[j]);
		}
}

void writeOutput()
{
	for(int i=0; i<n; ++i)
		cout << dist[i] << " ";
	cout << endl;
}

int main(){
	readInput();
	bellmanFord(0);
	writeOutput();
	return 0;
}