#include <vector>
#include <cstdio>
#include <string.h>

using namespace std;

#define Nmax 50010
vector <pair<int,int>> ad[Nmax] ;
int T[Nmax] , n , m , x , y , c ;
bool in_heap[Nmax];

struct heap
{
    int len ;
    int v[2 * Nmax] ;
};

heap h;


void push ( heap &h , int val )
{
    h.v[++h.len] = val ;
    for ( int nod = h.len ; nod > 1 && T[h.v[nod/2]] >= T[h.v[nod]] ; nod /= 2 )
        swap(h.v[nod/2],h.v[nod]);
}

void remake_heap ( heap &h , int nod )
{
    int l = 2 * nod ;
    int r = 2 * nod + 1 ;
    int m = nod ;
    if ( l <= h.len && T[h.v[m]] >= T[h.v[l]] ) m = l ;
    if ( r <= h.len && T[h.v[m]] >= T[h.v[r]] ) r = l ;
    if ( m != nod )
    {
        swap(h.v[m],h.v[nod]);
        remake_heap(h,m);
    }
}

void pop( heap &h )
{
    swap(h.v[1],h.v[h.len]);
    --h.len;
    remake_heap(h,1) ;
}

void Dijkstra ( int start )
{
    push(h,start);
    memset(T,0x3f,sizeof(T));
    T[start] = 0 ;
    //in_heap[start] = true ;
    while ( h.len > 0 )
    {
        int nod = h.v[1];
        pop(h);

        if ( in_heap[nod] ) continue;

        fprintf(stderr, "%d ", nod );

        for ( int i = 0 ; i < ad[nod].size() ; ++i )
        {
            if ( T[nod] + ad[nod][i].second < T[ad[nod][i].first] )
            {
                T[ad[nod][i].first] = T[nod] + ad[nod][i].second ;
                push(h,ad[nod][i].first);
            }
        }

        in_heap[nod] = true;
    }

    fprintf(stderr, "\n");
}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    scanf("%d %d",&n,&m);
    for ( int i = 1 ; i <= m ; i++ )
    {
        scanf("%d %d %d",&x,&y,&c);
        ad[x].push_back(make_pair(y,c));
        //ad[y].push_back(make_pair(x,c));
    }
    Dijkstra(1);
    for ( int i = 2 ; i <= n ; ++i )
    {
        if ( T[i] == 0x3f3f3f3f ) T[i] = 0 ;
        printf("%d ",T[i]);
    }
}