#include <fstream>
#include <queue>
#include <cstring>
#include <vector>

#define nod first
#define cost second

#define INF 0x3f3f3f

using namespace std;
int i,j,c,n,m,D[50005],ItNod[50005],Nod;
bool fv[50005];

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

vector < pair < int , int > > V[50005];
vector < pair < int , int > >::iterator it;
queue < int >Q;

int main()
{
    fin>>n>>m;
    for( int k = 1; k <= m; k++ )
    {
        fin>>i>>j>>c;
        V[ i ].push_back( make_pair ( j , c ) );
    }
   /// memset( D, INF, sizeof( D ) );
    for( i = 1 ; i < 50005 ; i++ )
        D[ i ] = INF;

    D[ 1 ] = 0;
    memset( ItNod, 0 , sizeof( ItNod ) );
    Q.push( 1 );
    fv[ 1 ] = true;

    while( !Q.empty( ) )
    {
        Nod = Q.front( );
        fv[ Nod ] = false;
        for( it = V[ Nod ].begin( ); it != V[ Nod ].end( ); it++ )
        {
            if( D[ ( *it ).nod ] > D[ Nod ] + ( *it ).cost  )
            {
                D[ (*it).nod ] = D[ Nod ] + ( *it ).cost;
                if( !fv[ (*it).nod ] )
                {
                    Q.push( (*it).nod );
                    fv[ (*it).nod ] = true;
                    if( ++ItNod[ ( *it ).nod ] > n )
                    {
                        fout<<"Ciclu negativ";
                        return 0;
                    }
                }
            }
        }
        Q.pop( );
    }
    for( i = 2; i <= n; i++ )
    {
        fout<<D[ i ] <<" ";
    }
    return 0;
}