#include<fstream>
#include<vector>
#include<algorithm>
#define INF (1 << 30)
#define pb push_back
#define mkp make_pair
#define pii pair<int, int>
#define nxt (*it).first
#define cst (*it).second
#define type pii
#define FORi(i,a,b)\
   for(int i=a; i<=b; ++i)
#define FOR(g)\
   for(vector<type>::iterator it=g.begin(); it!=g.end(); ++it)
#define infile "dijkstra.in"
#define outfile "dijkstra.out"
#define nMax 50005
using namespace std;

class heap{
    public:

    int *H, *Pos, *Priority;
    int  N;

    heap(int size){
        this->H = new int[size + 1];
        this->Pos = new int[size + 1];
        this->Priority = new int[size + 1];
        this->N  = 0;
    }

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

    void percolate(int k){
        while(k > 1 && Priority[H[k]] < Priority[H[k>>1]]){
            swap(Pos[H[k]], Pos[H[k>>1]]);
            swap(H[k], H[k>>1]);
            k>>=1;
        }
    }

    void sift(int k){
        int son = k, ls = k<<1, rs = ls + 1;

        if(ls <= N && Priority[H[ls]] < Priority[H[son]])
           son = ls;
        if(rs <= N && Priority[H[rs]] < Priority[H[son]])
           son = rs;

        if(son == k)
           return;

        swap(Pos[H[k]], Pos[H[son]]);
        swap(H[k], H[son]);
        sift(son);
    }

    void update(int x, int cost){
        if(cost < Priority[x]){
            Priority[x] = cost;
            percolate(Pos[x]);
        }
        else{
            Priority[x] = cost;
            sift(Pos[x]);
        }
    }

    void push(int x, int cost){
        H[++N] = x;
        Priority[x] = cost;
        Pos[x] = N;

        percolate(N);
    }

    int pop(){
        int top = H[1];
        H[1] = H[N--];
        Pos[H[1]] = 1;

        sift(1);

        return top;
    }
};

vector < type > v[nMax];

vector < int > Dist(nMax, INF);

int N, M;


void read(){
    ifstream f(infile);

    f >> N >> M;

    int x, y, cost;
    while(M--){
        f >> x >> y >> cost;
        v[x].pb(mkp(y, cost));
    }

    f.close();
}

void dijkstra(int src){
    heap H(N);

    Dist[src] = 0;
    H.push(1, 0);

    while(!H.empty()){
        int x = H.pop();

        FOR(v[x])
           if(Dist[x] + cst < Dist[nxt]){
               if(Dist[nxt] == INF)
                  H.push(nxt, Dist[nxt] = Dist[x] + cst);
               else
                  H.update(nxt, Dist[nxt] = Dist[x] + cst);
           }
    }
}

void print(){
    ofstream g(outfile);

    FORi(i,2,N)
       g << ((Dist[i] == INF) ? 0 : Dist[i]) << " ";

    g.close();
}

int main(){
    read();

    dijkstra(1);

    print();

    return 0;
}