#include <iostream>
#include <fstream>
#include <queue>
#define inf 1001

using namespace std;

ifstream fin ("bellmanford.in") ;
ofstream fout ("bellmanford.out") ;

int N , M ;

struct nod
{
    int info , cost ;
    nod * next ;
} ;

nod * L [50001] ;

void Citire ()
{
  fin >> N >> M ;
  int a , b , c ;
  while ( M >= 1 )
  {
      fin >> a >> b >> c ;
      nod * p = new nod ;
      p->info = b ;
      p->cost = c ;
      p->next = L [a] ;
      L [a] = p ;

      -- M ;
  }
}

int cst [50001] , iterari_nod [50001] , lg_c ;
bool in_coada [50001] ;
queue < int > coada ;

void BellmanFord ()
{
    // Initializare
    for ( int i = 2 ; i <= N ; ++ i )
           cst [i] = inf ;  // mai putin nodul sursa

    coada.push (1) ;
    in_coada [ 1 ] = true ;

    while ( !coada.empty() ) // cat timp sunt elemente in coada
    {
        int nd = coada.front () ;
        coada.pop () ;
        in_coada [ nd ] = false ;

        for ( nod * p = L [nd] ; p != 0 ; p = p->next )
        {
            if ( cst [p->info] > cst [nd] + p->cost )
                    cst [p->info] = cst [nd] + p->cost ; // minimizam distanta

            if ( in_coada [ p->info ] == 0 )  // nu se afla vecinul in coada
                    {
                        coada.push ( p->info ) ; // il introduc
                        in_coada [ p->info ] = true ;
                        ++ iterari_nod [ p->info ] ; // s-a trecut o data in plus prin el
                        if ( iterari_nod [ p->info ] > N ) // daca s-a trecut de mai mult de N ori prin el
                             {
                                 fout << "Ciclu negativ!\n" ;
                                 return ;
                             }
                    }
        }

    }

 for ( int i = 2 ; i <= N ; ++ i )
      fout << cst [i] << " " ;
}

int main()
{
    Citire () ;
    BellmanFord() ;
    return 0;
}