#include<stdio.h>
#include<vector>
#include<queue>
#include<bitset>

using namespace std ;

#define dim 50010
#define pb push_back
#define mp make_pair
#define fs first
#define sc second

vector < pair < int , int > > v[dim];
queue < int > q;
bitset < dim > in ;
int viz[dim];
long long int best[dim];
int n,m,x,y,c,cost;
void read()
{
    scanf("%d %d",&n,&m);
    for(int i=1;  i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        v[x].pb(mp(y,c));
    }

}
void afis (long long int a[dim] )
{
    for(int i=2  ;i<=n ; i++)
    printf("%lld ",a[i] ) ;
}
void solve()
{
    viz [ 1 ] = n;
    for( q.push(1) ; !q.empty () ; q.pop () )
    {
        x = q.front ();
       in[x] = 0;
        for(int i=0 ; i<v[x].size() ; i++ )
        {
            y = v[x][i].fs;
            cost = v[x][i].sc;
            if ( (best [ y ] > best[x] + cost || best [ y ] == 0  )&& viz[ y ] <= n  )
            {
                best [ y ] = best[x] + cost;
               // printf("%d ",y);
                viz[ y ]++;
                if ( in [ y ] == 0 )
                {
                in[y] = 1;
                q.push ( y );
                }
            }
            if ( viz[y] == n )
            while ( !q.empty() )
            q.pop() ;
        }
    }
    afis ( best ) ;
}
int main ()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    read();
    solve();
    return 0;
}