#include <bits/stdc++.h>

const int MAXN = 50000;
const int MAXM = 250000;
const int INF = 2000000000;

template <typename T> class Heap{
private:
    T heap[1 + MAXM];
    int last;

    inline int Heap_father(int p){ return p / 2;}
    inline int Heap_leftson(int p){ return 2 * p;}
    inline int Heap_rightson(int p){ return 2 * p + 1;}

    inline void Heap_upheap(int p){
        while(p != 1 && heap[Heap_father(p)] < heap[p]){
            std::swap(heap[p], heap[Heap_father(p)]);
            p = Heap_father(p);
        }
    }
    inline void Heap_downheap(int p){
        int pos = p;
        if(Heap_leftson(p) <= last  && heap[pos] < heap[Heap_leftson(p)])  pos = Heap_leftson(p);
        if(Heap_rightson(p) <= last && heap[pos] < heap[Heap_rightson(p)]) pos = Heap_rightson(p);
        if(pos != p){
            std::swap(heap[p], heap[pos]);
            Heap_downheap(pos);
        }
    }

public:
    inline void push(T val){
        heap[++last] = val;
        Heap_upheap(last);
    }
    inline void pop(){
        std::swap(heap[1], heap[last]);
        last--;
        Heap_downheap(1);
    }
    inline T top(){ return heap[1];}
    inline bool empty(){ return last == 0;}
};

struct Edge{
    int cost;
    int dest;

    bool operator <(const Edge &aux) const{
        return cost > aux.cost;
    }
};
std::vector <Edge> G[1 + MAXN];
Heap <Edge> pq;
int d[1 + MAXN];

int main(){
    FILE*fi,*fo;
    fi = fopen("dijkstra.in","r");
    fo = fopen("dijkstra.out","w");
    int n, m;
    fscanf(fi,"%d%d", &n, &m);
    for(int i = 0; i < m; i++){
        int a, b, c;
        fscanf(fi,"%d%d%d", &a, &b, &c);
        G[a].push_back({c, b});
    }
    for(int i = 0; i <= n; i++)
        d[i] = INF;

    pq.push({0, 1});
    while(!pq.empty()){
        int node = pq.top().dest, cost = pq.top().cost;
        if(d[node] == INF){
            d[node] = cost;
            for(int i = 0; i < G[node].size(); i++)
                if(d[G[node][i].dest] == INF)
                    pq.push({cost + G[node][i].cost, G[node][i].dest});
        }
        pq.pop();
    }

    for(int i = 2; i <= n; i++)
        if(d[i] == INF)
            fprintf(fo,"0 ");
        else
            fprintf(fo,"%d ", d[i]);

    fclose(fi);
    fclose(fo);
    return 0;
}