#include <iostream>
#include <queue>
#include <fstream>
#include <list>

using namespace std;

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

long long inf = 1000002;
priority_queue<pair<long long,long long>,vector<pair<long long ,long long>>,greater<pair<long long,long long>>> q;
vector <long long> d(50001,inf);
list <pair<long long,long long>> ad[50001];
int viz[50001];
int main()
{
    long long n, m;
    fin >> n >> m;
    for(long long i = 1; i <= m; i++)
    {

        long long a,b,c;
        fin >> a >> b >> c;
        ad[a].push_back(make_pair(b,c));
    }
    int s;
    s = 1;
    viz[s] = 1;
    d[s] = 0;
    q.push(make_pair(0,s));
    long long count = 0;
    while(!q.empty() && count < n*m)
    {


        pair <long long,long long> el = q.top();
        long long node = el.second;
        q.pop();
        viz[node] = 0;
        count ++;
        for(auto &edge: ad[node])
        {

            long long anode = edge.first;
            long long cost = edge.second;
            if(d[anode] > d[node] + cost)
            {

                d[anode] = d[node] + cost;
                if(!viz[anode])
                {

                    q.push(make_pair(d[anode],anode));
                }

            }
        }

    }
    ///verificam daca while-ul a fost intrerupt de a doua conditie => exista cicluri negative
    bool ciclu = false;
    for(long long i = 1; i<=n; i++)
        for(auto &edge: ad[i])
    {
         long long snode = edge.first;
         long long cost = edge.second;
         if(d[snode] > d[i] + cost)
                {ciclu = true;break;}
    }
    if(ciclu == true)
        fout<<"Ciclu negativ!";
    else
    {

        for(long long i = 2; i<=n; i++)
            fout<<d[i]<<" ";
    }
    return 0;
}