# include <fstream>
# include <iostream>
# define maxim 1<<30
using namespace std;
struct graf
{
    int nod, cost;
    graf *next;
};

int n, m;
graf *a[50001];
int dist[50001], h[50001], poz[50001], k;

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

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

}

void citire()
{
    ifstream in("dijkstra.in");
    int x, y, z;

    in>>n>>m;

    for (int i = 1; i <= m;i++)
    {
        in>>x>>y>>z;
        adauga(x, y, z);
    }
}

void swap(int x, int y)
{
    int t = h[x];
    h[x] = h[y];
    h[y] = t;
}

void upheap(int what) {

    int tata;
    while ( what > 1 ) {

        tata = what/2;
        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 f;
    while ( what <= k ) {
        f = what;
        if ( (what*2) <= k ) {
            f = what *2;
            if ( f + 1 <= k )
                if ( dist[ h[f + 1] ] < dist[ h[f] ] )
                    f++;
        }
        else
            return;

        if ( dist[ h[what] ] > dist[ h[f] ] )
        {
            poz[ h[what] ] = f;
            poz[ h[f] ] = what;

            swap(what, f);

            what = f;
        }
        else
            return;
    }
}

void dijkstra()
{

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

    while ( k ) {
        int min = h[1];
        swap(1, k);
        poz[ h[1] ] = 1;
        --k;
        downheap(1);

        graf *q = a[min];
        while ( q ) {
            if ( dist[q->nod] > dist[min] + q->cost ) {

                dist[q->nod] = dist[min] + q->cost;

                if ( poz[q->nod] != -1 )
                    upheap( poz[q->nod] );
                else
                {
                    h[++k] = q->nod;
                    poz[ h[k] ] = k;
                    upheap( k );
                }
            }
            q = q->next;
        }
    }
}

void afisare() {

    int i;
    ofstream out("dijkstra.out");

    for (i = 2; i <= n; ++i )
        if(dist[i]==maxim)
            out<<0<<" ";
        else
            out<<dist[i]<<" ";
    out<<'\n';

}


int main() {

    citire();
    dijkstra();
    afisare();

    return 0;
}