#include <iostream>
#include <vector>
#include <queue>
#include <utility>
#include <stdio.h>
#include <cassert>
#include <string.h>

#define INF 100000
using namespace std;

int N, M;

void Solve(std::vector <std::vector <std::pair <int, int> > > &G, int * Parent, int s, int dist[]) {

    std::priority_queue< std::pair<int, int>,
   	std::vector<std::pair<int, int> >, 
   	std::greater<std::pair<int, int> > > q;
  	
  	bool selectat[N];
  	
  	// initializare
  	for (int i = 1; i <= N; i++) {
  		selectat[i] = false;
  		dist[i] = INF;
  		Parent[i] = -1;
  	}
  	
  	dist[s] = 0;  
    selectat[s] = true;
    
    for (unsigned int i = 0; i < G[s].size(); i++) {
    
    	int v = G[s][i].first;
    	
    	dist[v] = G[s][i].second;
    	q.push(std::make_pair(G[s][i].second, v));
    	Parent[v] = s;
    }
    
  
    
    while (!q.empty()) {
    	
    	int u = (q.top()).second;
    	int cost = (q.top()).first;
    	q.pop();
    	
    	if (cost != dist[u]) continue;
    	
    	selectat[u] = true;
    	
    	for (unsigned int i = 0; i < G[u].size(); i++) {
    		
    		if (selectat[G[u][i].first] == false && dist[G[u][i].first] > (dist[u] + G[u][i].second)) {
  
    			dist[G[u][i].first] = dist[u] + G[u][i].second;
    			Parent[G[u][i].first] = u;
    				
    			q.push(std::make_pair(dist[G[u][i].first], G[u][i].first)); // actualizez costul nou
    		}
    	}	
    }
}


int main() {
	
	int x, y, c;
	
	FILE* fin = fopen("dijkstra.in", "r");
	FILE* fout = fopen("dijkstra.out", "w"); 
	
	assert(fscanf(fin, "%d %d", &N, &M) == 2);
	
	std::vector<std::vector<std::pair<int, int> > > G(N + 1);
	int dist[N + 1];
	
	for (int i = 0; i < M; i++) {
	
		assert(fscanf(fin, "%d %d %d", &x, &y, &c) == 3);
		
		G[x].push_back(std::make_pair(y, c));
    
		
	}
	fclose(fin);
	
	int Parent[1000000];
	memset(Parent, 0, sizeof(int) * (N + 1));
	
	Solve(G, Parent, 1, dist);
	
	for (int i = 2; i <= N; i++) {
		if (dist[i] == INF) {
			fprintf(fout, "0 ");
		}
		else {
			fprintf(fout, "%d ", dist[i]);
		}
	}
	
	fclose(fout);
}