#include <fstream>
#include <vector>
#include <queue>

std::ifstream fin("dijkstra.in");
std::ofstream fout("dijkstra.out");

typedef std::pair<int, int> pii;
const int INF = 1e9;

int N, M;
std::vector<std::vector<pii> > G;
std::vector<int> D;

class MaxHeap{
private:
    std::vector<pii> v;
    int dim;

public:
    MaxHeap() : dim(0), v(std::vector<pii>(2 * N + 3)) {}
    MaxHeap(pii p) : dim(1), v(std::vector<pii>(2 * N + 3, p)) {}

    void push(pii t){
        v[++dim] = t;
        int p = dim;
        while(p != 1 && v[p] > v[p >> 1]){
            std::swap(v[p], v[p >> 1]);
            p >>= 1;
        }
    }

    pii top(){
        return v[1];
    }

    void pop(){
        std::swap(v[1], v[dim--]);
        int t = 1;
        while((t << 1) <= dim) {
            int child = t << 1;
            if(child + 1 <= dim && v[child + 1] > v[child])
                child++;
            if(v[t] >= v[child])
                break;
            std::swap(v[t], v[child]);
            t = child;
        }
    }

    bool empty(){
        return dim == 0; 
    }
};

int main(){
    fin >> N >> M;

    G.resize(N + 1);
    D.resize(N + 1, INF);

    for(int x, y, c; M--;){
        fin >> x >> y >> c;
        G[x].push_back({y, c});
    }

    D[1] = 0;
    MaxHeap maxHeap({0, 1});

    while(!maxHeap.empty()){
        int node = maxHeap.top().second;
        maxHeap.pop();

        for(pii p : G[node]){
            if(D[p.first] > D[node] + p.second){
                D[p.first] = D[node] + p.second;
                maxHeap.push({D[p.first], p.first});
            }
        }
    }

    for(int i = 2; i <= N; ++i){
        if(D[i] == INF){
            fout << "0 ";
        }
        else{
            fout << D[i] << ' ';
        }
    }
}