#include<fstream>
#include<vector>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int ok,i,n,m,a,b,co,st,dr;
int dn[50001],c[50001],hz[50001],v[2500001];
vector< pair<int,int> > h[50001];
int main(){
    in >> n >> m;
    for( i = 1; i <= m; i ++ ){
        in >> a >> b >> co;
        h[a].push_back( make_pair( b,co ) );
    }
    v[1] = 1;
    dn[1] = 1;
    hz[1] ++;
    for( st = 1, dr = 1; st <= dr; st ++ ){
        for( i = 0; i < h[v[st]].size(); i ++ ){
            if( hz[ h[v[st]][i].first ] <n&& (c[ h[v[st]][i].first ] > c[v[st]] + h[v[st]][i].second || hz[ h[v[st]][i].first ] == 0) ){
                if( dn[ h[v[st]][i].first ] == 0 ){
                    dn[h[v[st]][i].first] = 1;
                    dr++;
                    v[dr] = h[v[st]][i].first;
                    c[h[v[st]][i].first] = c[v[st]] + h[v[st]][i].second;
                    hz[h[v[st]][i].first]++;
                }
                else{
                    c[h[v[st]][i].first] = c[v[st]] + h[v[st]][i].second;
                }
            }
        }
        dn[v[st]] = 0;
    }
    for( i = 2; i <= n; i ++ ){
        if( hz[i] == n ){
            ok = 1;
            break;
        }
    }
    if( ok == 1 ){
        out<<"Ciclu negativ!";
    }
    else
    for( i = 2; i <= n; i ++ ){
        out<<c[i]<<" ";
    }
    return 0;
}