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

using namespace std;
ifstream f("bellmanford.in");
ofstream g("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 rel[50001];

int viz[50001];
int main()
{
    long long n, m;
    f >> n >> m;
    for(long long i = 1; i <= m; i++)
    {
        long long a,b,c;
        f >> 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));
    bool ciclu = false;
    while(!q.empty() && !ciclu)
    {
        pair <long long,long long> el = q.top();
        long long node = el.second;
        q.pop();
        viz[node] = 0;
        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])
                {
                    rel[anode] ++;
                    if(rel[anode] > n - 1)
                    {
                        ciclu = true;
                    }
                    q.push(make_pair(d[anode],anode));
                }
            }
        }
    }
    if(ciclu == true)
        g<<"Ciclu negativ!";
    else
    {
        for(long long i = 2; i<=n; i++)
            g<<d[i]<<" ";
    }
    return 0;

}