#include <fstream>
#include <queue>
#include <vector>
using namespace std;

#define INF 1000000000
#define NMAX 50001

int n,x0;
vector < pair<int,int> > G[NMAX];
int dmin[NMAX],nr[NMAX];
bool negativ;
queue <int> C;

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

void citire()
{
    int i,m,x,y,c;
    f>>n>>m;
    x0=1;
    for(i=0;i<m;i++)
    {
        f>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
}

void bellman_ford()
{
    int i,x;
    for(i=1;i<=n;i++)
        dmin[i]=INF;
    dmin[x0]=0;
    C.push(x0);

    while(!C.empty() && !negativ)
    {
        x=C.front();
        C.pop();
        for(auto& it : G[x])
        {
            if(dmin[it.first]>dmin[x]+it.second)
            {
               dmin[it.first]=dmin[x]+it.second;
               nr[it.first]++;
               C.push(it.first);
               if(nr[it.first]>n) negativ=1;
            }
        }
    }

}

void afisare()
{
    if(negativ)
        g<<"Ciclu negativ!\n";
    else
    {
        for(int i=1;i<=n;i++)
        {
            if(i!=x0)
                g<<(dmin[i]!=INF?dmin[i]:0)<<" ";
        }
        g<<"\n";
    }
}

int main()
{
    citire();
    bellman_ford();
    afisare();

    f.close();
    g.close();
    return 0;
}