#include <algorithm>
#include <fstream>
#include <cstring>
#include <set>
#include <vector>
#include <iostream>

using namespace std;

#define INF 99999999
#define MAX 9990000


vector<pair < int, int>> graph[MAX];

int dist[MAX];


int main(){
    ifstream be("dijkstra.in");
    ofstream ki("dijkstra.out");



    int n, m, to, from, cost;

    be >> n >> m;

    for(int i = 1; i <= m; i++){
        be >> from >> to >> cost;
        graph[from].push_back(make_pair(to, cost));

    }
    for(int i = 1; i <= m; i++){
        dist[i] = INF;
    }
    dist[1] = 0;
    set<pair<int, int>> heap;
    heap.insert(make_pair(0, 1));
    while(!heap.empty()) {
        int node = heap.begin() -> second;
        int distance = heap.begin() -> first;
        heap.erase(heap.begin());
        for(vector<pair<int, int>>::iterator it = graph[node].begin(); it != graph[node].end(); it++){

            to = it -> first;
            cost = it -> second;
            if(dist[to] > dist[node] + cost){
                if(dist[to] != INF){
                    heap.erase(heap.find(make_pair(dist[to], to)));
                }
                dist[to] = dist[node] + cost;
                heap.insert(make_pair(dist[to], to));
            }
        }

    }
    for(int i = 2; i <= n;i++){
        if(dist[i] == INF){
                dist[i] = 0;
        }
            ki << dist[i] << " ";

    }



}