#include<fstream>
#include<queue>
#include<vector>
#include<utility>
#include<algorithm>


#define NN 50009
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define INF 0x3f3f3f3f


using namespace std;
ofstream out("bellmanford.out");

int n , m ;

vector< pair < int , int > >G[NN];
typedef vector< pair < int , int > >:: iterator IT;

vector< int > dist;

queue< int > Q;


void read();
int bm( int root );
void wrs();

int main()
{
    read();
    wrs();

    return 0;
}

void read()
{
    ifstream in("bellmanford.in");
    in >> n >> m;
    for( int x , y , cost ;  m ; --m )
    {
        in >> x >> y >> cost;
        G[x].pb ( mp ( y , cost ) );
    }
}

int bm( int start )
{
    dist.resize( n+1, INF );
    dist[ start ] = 0;
    Q.push( start );


    int k ;

        while( !Q.empty() )
        {
            k = Q.front();

            Q.pop();

            int val = dist[k];
                for( IT i = G[k].begin(); i!= G[k].end(); ++i )
                    if ( dist[ i->f ] > val + i->s )
                    {
                        dist[ i->f ] = val + i->s;
                        Q.push( i->f );
                    }
                    else
                        if ( dist[ i->f ] > 0 && val < 0 )
                            return 0;
        }
    return 1;
}

void wrs()
{
    if ( !bm(1) )
        out << "Ciclu negativ!" ;
        else
            for( int i=2 ; i<=n ; i++)
                out << ( dist[i] == INF ? 0 : dist[i] ) << " ";
}