#include <fstream>
#include <queue>
#include <vector>
#define MAX 2100000000

using namespace std;

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

struct A
{
    int dest, cost;
};

queue < int > q;
vector < A > v[50005];
int r[50005];
bool viz[50005];

int main()
{
    int n, m, i, x, y, z;

    fin >> n >> m;
    while ( m-- )
    {
        fin >> x >> y >> z;
        v[x].push_back ( { y, z } );
    }

    for ( i = 2 ; i <= n ; i++ ) r[i] = MAX;

    q.push ( 1 );
    viz[1] = 1;
    while ( q.empty() == 0 )
    {
        x = q.front();
        q.pop();

        for ( i = 0 ; i < v[x].size() ; i++ )
            if ( viz[v[x][i].dest] == n - 1 )
            {
                fout << "Ciclu negativ!";
                return 1;
            }
            else if ( r[x] + v[x][i].cost < r[v[x][i].dest] )
            {
                r[v[x][i].dest] = r[x] + v[x][i].cost;
                viz[v[x][i].dest]++;
                q.push ( v[x][i].dest );
            }
    }

    for ( i = 2 ; i <= n ; i++ ) fout << r[i] << ' ';

    return 0;
}