/// Craciun Catalin
///  Dijkstra
#include <iostream>
#include <fstream>

#define NMax 200005
#define inf 1<<30

using namespace std;

struct graf {

    int cost;
    int nod;
    graf *next;
    graf() {
        cost = nod = 0;
        next = NULL;
    }
};

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, m;
graf *a[NMax];
int k;
int H[NMax];
int dist[NMax], poz[NMax];

void add(int where, int what, int cost) {

    graf *aux = new graf;
    aux -> cost = cost;
    aux -> nod = what;
    aux -> next = a[where];
    a[where] = aux;
}

void read() {

    f>>n>>m;
    for (int i=1;i<=m;i++) {
        int x, y, c;
        f>>x>>y>>c;
        add(x,y,c);
    }
}

void swap(int i, int j) {

    int aux = H[i];
    H[i] = H[j];
    H[j] = aux;
}

void upHeap(int what)
{
    int tata;
    while ( what > 1 )
    {
        tata = what >> 1;

        if ( dist[ H[tata] ] > dist[ H[what] ] )
        {
            poz[ H[what] ] = tata;
            poz[ H[tata] ] = what;

            swap(tata, what);

            what = tata;
        }
        else
            what = 1;
    }
}

void downHeap(int what)
{
    int w;
    while ( what <= k )
    {
        w = what;
        if ( (what<<1) <= k )
        {
            w = what << 1;
            if ( w + 1 <= k )
                if ( dist[ H[w + 1] ] < dist[ H[w] ] )
                    ++w;
        }
        else
            return;

        if ( dist[ H[what] ] > dist[ H[w] ] )
        {
            poz[ H[what] ] = w;
            poz[ H[w] ] = what;

            swap(what, w);

            what = w;
        }
        else
            return;
    }
}

void dijkstra() {

    for (int i=2;i<=n;i++) {
        dist[i] = inf;
        poz[i] = -1;
    }

    k = 1;
    H[1] = 1;
    poz[1] = 1;
    dist[1] = 0;
    while ( k != 0 ) {

        int extracted = H[1];
        swap (1, k);
        poz[ H[1] ] = 1;
        k--;

        downHeap(1);

        graf *q = a[extracted];
        while ( q ) {
            if (dist[q->nod] > q->cost + dist[extracted]) {
                dist[q->nod] = q->cost + dist[extracted];
                if (poz[q->nod] != -1)
                    upHeap(poz[q->nod]);
                else {
                    H[++k] = q->nod;
                    poz[ H[k] ] = k;
                    upHeap( k );
                }
            }

            q = q->next;
        }
    }
}

int main() {

    read();
    dijkstra();
    for (int i=2;i<=n;i++) {
        if (dist[i] != inf)
            g<<dist[i]<<' ';
        else
            g<<0<<' ';
    }

    f.close(); g.close();

    return 0;
}