#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#include <climits>

struct Muchie{
    int capat;
    int cost;
};

const int INF = INT_MAX;

int main()
{
    std::ifstream in("dijkstra.in");
    std::ofstream out("dijkstra.out");

    int N;
    int M;
    in >> N >> M;

    std::vector<Muchie> Graph[N + 1];
    for(int i = 1; i <= M; ++i){
        int nod1;
        int nod2;
        int cost;
        in >> nod1 >> nod2 >> cost;
        Graph[nod1].push_back({nod2, cost});
    }

    //punctul de start este 1, conform problemei
    std::priority_queue< int, std::vector<int>, std::greater<int> > pri_queue;
    pri_queue.push(1);

    int dist[N + 1];
    for(int i = 1; i <= N; ++i){
        dist[i] = INF;
    }
    bool in_coada[N + 1];
    in_coada[1] = true;
    dist[1] = 0;

    while(!pri_queue.empty()){
        int nod_curr = pri_queue.top();
        pri_queue.pop();
        std::cout << nod_curr;
        in_coada[nod_curr] = false;
        for(int j = 0; j < Graph[nod_curr].size(); ++j){
            int cost = Graph[nod_curr][j].cost;
            int capat = Graph[nod_curr][j].capat;
            int tmp = dist[nod_curr] + cost;
            if(dist[capat] > tmp){
                dist[capat] = tmp;
                if(!in_coada[capat]){
                    pri_queue.push(capat);
                    in_coada[capat] = true;
                }
            }
        }
    }

    for(int i = 2; i <= N; ++i){
        if(dist[i] == INF){
            out << 0 << ' ';
        }
        else{
            out << dist[i] << ' ';
        }
    }
    return 0;
}