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

using namespace std;

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

void BellManFord ( int start )
{
    q.push(start);
    in_queue[start] = true ;
    memset(T,0x3f,sizeof(T)) ;
    T[start] = 0 ;
    while ( !q.empty() )
    {
        int nod = q.front();
        q.pop();
        in_queue[nod] = false ;
        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 ;
                if ( !in_queue[ad[nod][i].first] )
                {
                    q.push(ad[nod][i].first) ;
                    in_queue[ad[nod][i].first] = true ;
                }
            }
        }
    }
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.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));
    }
    BellManFord(1) ;
    for ( int i = 2 ; i <= n ; i++ )
    {
        printf("%d ",T[i]) ;
    }

}