#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

const int N = 50001;
vector <pair <int, int> > v[N];
int costmin[N], ap[N];
bool curent[N];
queue <int> q;

int main ()
{
    int n, m;
    bool ciclu = false;
    in >> n >> m;
    for ( int i = 2; i <= n; i++ )
    {
        costmin[i] = 999999999;
    }
    for ( int i = 1; i <= m; i++ )
    {
        int x;
        pair <int , int > y;
        in >> x >> y.first >> y.second;
         v[x].push_back (y) ;
    }
    q.push(1);
    curent[1] = true;
    while (!q.empty() && !ciclu )
    {
        int x = q.front();
        for ( auto y : v[x] )
        {
            if ( costmin[x] + y.second < costmin[y.first] )
            {
                if ( !curent[y.first])
                {
                    q.push ( y.first );
                    curent[y.first] = true;
                    ap[y.first]++;
                    if ( ap[y.first] == n )
                    {
                        ciclu = true;
                        break;
                    }
                }
                costmin[y.first] = costmin[x] + y.second;
            }
        }
        curent[x] = false;
        q.pop();
    }
    if ( ciclu )
    {
        out << "Ciclu negativ!";
    }
    else
    {
        for ( int i = 2; i <= n; i++ )
        {
            out << costmin[i] << " ";
        }
    }
    return 0;
}