#include <bits/stdc++.h>
#define pp pair< int, int >
#define x first
#define y second

using namespace std;

const int mxn = 50 * 1000 + 10;

vector< pp > v[ mxn ];
int d[ mxn ], nr[ mxn ];
bool viz[ mxn ];

int n, m;

int bellman(){
    queue< int > q;
    q.push( 1 );
    while(!q.empty() && nr[ q.front() ] < n){
        int nx = q.front();
        q.pop();
        viz[ nx ] = 0;
        for(auto it: v[ nx ])
            if(d[ nx ] + it.y < d[ it.x ]){
                d[ it.x ] = d[ nx ] + it.y;
                if(viz[ it.x ] == 0){
                    viz[ it.x ] = 1;
                    q.push( it.x );
                    nr[ it.x ]++;
                }
            }
    }
    return q.size();
}

int main()
{
    ios_base::sync_with_stdio( false );
    cin.tie( 0 );
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    cin>> n >> m;
    for(int i = 0, xx, yy, zz; i < m; i++){
        cin>> xx >> yy >> zz;
        v[ xx ].push_back(make_pair(yy, zz));
    }
    for(int i = 2; i <= n; i++)
        d[ i ] = INT_MAX;
    nr[ 1 ] = viz[ 1 ] = 1;
    if(bellman())
        cout<< "Ciclu negativ!";
    else
        for(int i = 2; i <= n; i++)
            cout<< d[ i ] << ' ';
    return 0;
}