#include <iostream>
#include <vector>
#include <set>

using namespace std;

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


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

void dijkstra(int s){
	dist[s] = 0;
	for(int i=0; i<n; ++i) 
		if(i!=s)
			dist[i] = INF;
	for(int i=0; i<n; ++i)
		q.insert(pii(dist[i], i));
	while(!q.empty())
	{
		set<pii> :: iterator it = q.begin();
		int u = it->second;
		q.erase(it);
		for(int i=0; i<adj[u].size(); ++i){
			int v = adj[u][i];
			q.erase(pii(dist[v], v));
			dist[v] = min(dist[v], dist[u]+w[u][i]);
			q.insert(pii(dist[v], v));
		}
	}
}

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

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