#include <cstdio>

 

const int maxn = 50001;

const int inf = 1 << 30;

 

FILE *in = fopen("dijkstra.in","r"), *out = fopen("dijkstra.out","w");

 

struct graf

{

int nod, cost;

graf *next;

};

 

int n, m;

graf *a[maxn];

int d[maxn], h[maxn], poz[maxn], k;

 

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

{

graf *q = new graf;

q->nod = what;

q->cost = cost;

q->next = a[where];

a[where] = q;

}

 

void read()

{

fscanf(in, "%d %d", &n, &m);

 

int x, y, z;

for ( int i = 1; i <= m; ++i )

{

fscanf(in, "%d %d %d", &x, &y, &z);

add(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 >> 1;

 

if ( d[ h[tata] ] > d[ 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<<1) <= k )

    {

    f = what << 1;

    if ( f + 1 <= k )

    if ( d[ h[f + 1] ] < d[ h[f] ] )

    ++f;

    }

    else

    return;

     

    if ( d[ h[what] ] > d[ h[f] ] )

    {

    poz[ h[what] ] = f;

    poz[ h[f] ] = what;

     

    swap(what, f);

     

    what = f;

    }

    else

    return;

    }

    }

     

    void dijkstra_heap()

    {

    for ( int i = 2; i <= n; ++i )

    d[i] = inf, 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 ( d[q->nod] > d[min] + q->cost )

    {

    d[q->nod] = d[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;

    }

    }

    }

     

    int main()

    {

    read();

    dijkstra_heap();

     

    for ( int i = 2; i <= n; ++i )

    fprintf(out, "%d ", d[i] == inf ? 0 : d[i]);

    fprintf(out, "\n");

     

    return 0;

    }