#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;} //tatal nodului p din arbore
    inline int Heap_leftson(int p){ return 2 * p;} //fiul stang al nodului p din arbore
    inline int Heap_rightson(int p){ return 2 * p + 1;} //fiul drept al nodului p din arbore

    inline void Heap_upheap(int p){ //incercam sa deplasam nodul p in sus
        while(p != 1 && heap[Heap_father(p)] < heap[p]){ //daca avem prioritate mai mare decat tatal
            std::swap(heap[p], heap[Heap_father(p)]);
            p = Heap_father(p);
        }
    }
    inline void Heap_downheap(int p){ //incercam sa deplasam nodul p in jos
        int pos = p; //pozitia pe care va ajunge nodul p
        if(Heap_leftson(p) <= last  && heap[pos] < heap[Heap_leftson(p)])  pos = Heap_leftson(p); //daca e mai bun fiul stang
        if(Heap_rightson(p) <= last && heap[pos] < heap[Heap_rightson(p)]) pos = Heap_rightson(p);//daca e mai bun fiul drept
        if(pos != p){ //daca noua pozitie este diferita de cea initiala
            std::swap(heap[p], heap[pos]);
            Heap_downheap(pos);
        }
    }

public:
    inline void push(T val){ //introducem o noua valoare in heap
        heap[++last] = val;
        Heap_upheap(last);
    }
    inline void pop(){ //eliminam varful heapului
        std::swap(heap[1], heap[last]);
        last--;
        Heap_downheap(1);
    }
    inline T top(){ return heap[1];} //elementul din varful heapului
    inline bool empty(){ return last == 0;} //daca heapul este gol
};

struct Edge{ //stuctura care reprezinta o muchie
    int cost;
    int dest;

    bool operator <(const Edge &aux) const{ //comparator care da prioritatea muchiei
        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; //initial distanta pana la oricare nod este infinita

    pq.push({0, 1});
    while(!pq.empty()){
        int node = pq.top().dest, cost = pq.top().cost; //alegem muchia de cost minim
        pq.pop(); //elimimam muchia curenta
        if(d[node] == INF){ //daca ea este intr-adevar buna
            d[node] = cost;
            for(int i = 0; i < G[node].size(); i++) //verificam toti vecinii
                if(d[G[node][i].dest] == INF) //introducem toate muchiile bune in heap
                    pq.push({cost + G[node][i].cost, G[node][i].dest});
        }
    }

    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;
}