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

using namespace std;

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

const int inf= 1<<30;
const int nmax= 50000;

struct str {
    int x, y;
};

inline str mp( int x, int y ) {
    str sol;
    sol.x= x, sol.y= y;
    return sol;
}

int w[nmax+1], f[nmax+1];

queue <int> q;
vector <str> g[nmax+1];

int main(  ) {
    int n, m;
    fin>>n>>m;
    for ( int i= 1; i<=m; ++i ) {
        int x, y, z;
        fin>>x>>y>>z;
        g[x].push_back( mp( y, z ) );
    }
    w[1]= 0;
    for ( int i= 2; i<=n; ++i ) w[i]= inf;
   
    int ok= 1;
    for ( q.push(1); !q.empty() && ok==1; q.pop() ) {
        int x= q.front();
        ++f[x];
        if ( f[x]>=n ) ok= 0;
        for ( int j= 0; j<(int)g[x].size() && ok==1; ++j ) {
            if ( w[x]+g[x][j].y<w[g[x][j].x] ) {
                w[g[x][j].x]= w[x]+g[x][j].y;
                q.push(g[x][j].x);
            }
        }
    }

    if ( ok==0 )
        fout<<"Ciclu negativ!";
    else for ( int i= 2; i<=n; ++i ) fout<<w[i]<<" ";
    fout<<"\n";

    return 0;
}