#include <bits/stdc++.h>
 
using namespace std;
 
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
 
const int INF = 1e9;
 
vector <pair <int, int>> adj[50001];
 
bitset <50001> u;
 
int d[50001], p[50001];
int N, M;
 
void dijkstra(int s) {
    for(int i = 1;i <= N;i++)
    	d[i] = INF, p[i] = -1;
 
    d[s] = 0;
    set <pair <int, int>> q;
    q.insert({0, s});

    while(!q.empty()){
    	int v = q.begin() -> second;
    	q.erase(q.begin());

    	for(auto edge : adj[v]){
    		int to = edge.first;
    		int len = edge.second;

    		if(d[v] + len < d[to]){
    			q.erase({d[to], to});
    			d[to] = d[v] + len;
    			p[to] = v;
    			q.insert({d[to], to});
    		}
    	}
    }
}
 
int main(){
 
	fin >> N >> M;
	while(M--){
		int x, y, val;
		fin >> x >> y >> val;
		adj[x].emplace_back(y, val);
	}
 
	dijkstra(1);
 
	for(int i = 2;i <= N;i++){
		if(d[i] == INF) d[i] = 0;
		fout << d[i] << " ";
	}
}