#include <iostream>

using namespace std;

const int MAXN = 1000 + 10;
const int INF = 1000*1000*1000;

int n, m;
int adj[MAXN][MAXN];
int w[MAXN][MAXN];
int dist[MAXN];
int mark[MAXN];

void readInput(){
	cin >> n >> m;
	for(int i=0; i<m; ++i){
		int v, u, z;
		cin >> u >> v >> z;
		adj[u][v] = 1;
		w[u][v] = z;
	}
}

void dijkstra(int s){
	dist[s] = 0;
	for(int i=0; i<n; ++i) 
		if(i!=s)
			dist[i] = INF;
	for(int rep=0; rep<n; ++rep)
	{
		int u = -1;
		int du = INF;
		for(int i=0; i<n; ++i)
			if(!mark[i] && dist[i] <= du){
				u = i;
				du = dist[i];
			}
		mark[u] = 1;
		for(int v=0; v<n; ++v)
			if(adj[u][v])
				dist[v] = min(dist[v], dist[u]+w[u][v]);
	}
}

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

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