#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

#define int long long

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


const int MAX=5e4;
int n,m,i,j,cost,d[MAX+5],fr[MAX+5];
vector <pair<int,int>> muchii[MAX+5];
priority_queue < pair<int,int>, vector<pair<int,int>>,greater<pair<int,int>>> q;
bool in_queue[MAX+5],negative_cycle=0;

signed main()
{
    fin>>n>>m;
    while (m)
    {
        fin>>i>>j>>cost;
        muchii[i].push_back({j,cost});
        m--;
    }

    for (i=1; i<=n; i++)
        d[i]=2e12;

    d[1]=0; in_queue[1]=1; fr[1]++; q.push({0,1});
    while (!q.empty() && !negative_cycle)
    {
        int nod=q.top().second;
        q.pop(); in_queue[nod]=0;

        for (auto x: muchii[nod])
        {
            int nod2=x.first,costmuchie=x.second;

            if (d[nod2]>d[nod]+costmuchie)
            {
                d[nod2]=d[nod]+costmuchie;

                q.push({d[nod]+costmuchie,nod2});
                in_queue[nod2]=1;
                fr[nod2]++;

                if (fr[nod2]>n)
                negative_cycle=1;
            }
        }
    }

    if (negative_cycle)
    fout<<"Ciclu negativ!";
    else
    {
        for (i=2; i<=n; i++)
            fout<<d[i]<<" ";
    }
    return 0;
}