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

using namespace std;

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

#define nmax 50001
#define infinite 100000000

vector <pair <int, int>> a[nmax];
queue <int> coada;
int nodcurent,cost,vecin,i,j,n,m,k1,k2,k3;
int d[nmax],repetitie[nmax];
bool ex[nmax];

bool bellman(int s)
{
    coada.push(s); ex[s]=1; d[s]=0;
    while(coada.empty()==0)
    {
        nodcurent=coada.front();
        coada.pop(); ex[nodcurent]=0;
        if(repetitie[nodcurent]>n)
            return 1;
        repetitie[nodcurent]++;
        for(unsigned int i=0; i<a[nodcurent].size();i++)
        {
            vecin=a[nodcurent][i].first;
            cost=a[nodcurent][i].second;
            if(d[vecin]>d[nodcurent]+cost)
            {
                d[vecin]=d[nodcurent]+cost;
                if(ex[vecin]==0)
                {
                    coada.push(vecin);
                    ex[vecin]=1;
                }
            }
        }
    }
    return 0;
}

int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>k1>>k2>>k3;
        a[k1].push_back(make_pair(k2,k3));
    }
    for(i=1;i<=n;i++)
        d[i]=infinite;


    if(bellman(1)==0)
    for(i=2;i<=n;i++)
        g<<d[i]<<" ";
        else g<<"Ciclu negativ!";

    return 0;
}