#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream in ("bellmanford.in");
ofstream out ("bellmanford.out");
const int NMax = 5005;
int n,m,cont;
int V[NMax],Num[NMax],Qr[NMax];
vector<pair<int,int> > G[NMax];
queue <int> Q;
void Solve ()//void BellmanFord()
{
    Q.push(1);
    V[1]=0;
    while (!Q.empty())
    {
        int Nod = Q.front();
        Q.pop();
        for (int i=0;i<G[Nod].size();i++)
        {
            int Vecin = G[Nod][i].first;
            int Cost = G[Nod][i].second;
            if (V[Vecin]-Cost>V[Nod])
            {
                V[Vecin]=V[Nod]+Cost;
                if (!Qr[Vecin])
                {
                    Qr[Vecin]=1;
                    Num[Vecin]++;
                    Q.push(Vecin);
                    if (Num[Vecin]>n)
                    {
                        cont=1;
                        return;
                    }
                }
            }
        }
        Qr[Nod]=0;
    }
}
void Read()
{
    in>>n>>m;
    for (int i=1;i<=n;i++)
        V[i]=INT_MAX;
    for (int i=0;i<m;i++)
    {
        int n1,n2,c;
        in>>n1>>n2>>c;
        G[n1].push_back(make_pair(n2,c));
    }
}
void Print()
{
    if (cont)
    {
        out<<"Ciclu negativ!"<<'\n';
    }
    else
    {
        for (int i=2;i<=n;i++)
        {
            out<<V[i]<<' ';
        }
    }
}
int main()
{
    Read();
    Solve();
    Print();
    return 0;
}