// Simionescu Andrei, 3/23/2010
// http://infoarena.ro/problema/dijkstra
// Dificultate: EASY->MEDIUM
// Categorii: grafuri, heapuri binare

#include <cstdio>
using namespace std;

#define NMAX  50001
#define MAXINT  1<<30

typedef struct graf{
    int nod, cost;
    struct graf * next;
} graf;

int n, m;
int d[NMAX], h[NMAX], poz[NMAX], k;
graf * a[NMAX];

void add(int,int,int);
void read(); void write();
void swap(int,int);
void heapify_up(int);
void heapify_down(int);
void dijkstra_heap();

// Main
int main(){
	
    read();
	dijkstra_heap();
	write();	
	
    return 0;
}


// Adds a node to the graph
void add( int pos, int val, int cost )
{
    graf *q = new graf;
    
    q->nod = val;
    q->cost = cost;
    q->next = a[pos];
    
    a[pos] = q;
}	

// Reads the input data and adds the nodes to the graph
void read()
{
    freopen( "dijkstra.in", "r", stdin );
    scanf( "%d %d", &n, &m );

    int x, y, z;
    
    for ( int i = 1; i <= m; ++i )
    {
        scanf( "%d %d %d", &x, &y, &z);
        add( x, y, z );
    }
}

// Swaps 2 heap positions
void swap(int x, int y)
{
    int t = h[x];
    h[x] = h[y];
    h[y] = t;
}

// Heapify-up
void heapify_up( int val )
{
    int tata;
    while( val > 1 )
    {
        tata = val >> 1;

        if ( d[ h[tata] ] > d[ h[val] ] )
        {
            poz[ h[val] ] = tata;
            poz[ h[tata] ] = val;

            swap(tata, val);

            val = tata;
        }
        else
            val = 1;
    }
}

// Heapify-down
void heapify_down(int val)
{
    int f;
    while ( val <= k )
    {
        f = val;
        if ( (val<<1) <= k )
        {
            f = val << 1;
            if ( f + 1 <= k )
                if ( d[ h[f + 1] ] < d[ h[f] ] )
                    ++f;
        }
        else
            return;

        if ( d[ h[val] ] > d[ h[f] ] )
        {
            poz[ h[val] ] = f;
            poz[ h[f] ] = val;

            swap(val, f);

            val = f;
        }
        else
            return;
    }
}

// Solves the problem
void dijkstra_heap()
{
    for ( int i = 2; i <= n; ++i )
        d[i] = MAXINT, poz[i] = -1;
    poz[1] = 1;

    h[++k] = 1;

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

        heapify_down(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 )
                    heapify_up( poz[q->nod] );
                else
                {
                    h[++k] = q->nod;
                    poz[ h[k] ] = k;
                    heapify_up( k );
                }
            }
            q = q->next;
        }
    }
}

// Writes the output
void write(){
    freopen( "dijkstra.out", "w", stdout );
    
    for ( int i = 2; i <= n; ++i )
        printf( "%d ", d[i] == MAXINT ? 0 : d[i]);
    printf( "\n" );

    
}