#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50001
#define INFINIT 1000000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector <pair <int,int> > G[NMAX];
queue <int> c;
int n,prec[NMAX],xs,nr[NMAX],negativ;
int cmin[NMAX];
void citire();
void bellman();
void afisare();
int main()
{
    int i;
    citire();
    for (i=1; i<=n; i++) cmin[i]=INFINIT;
    //for (i=0; i<G[xs].size(); i++) cmin[G[xs][i].first]=G[xs][i].second;
    cmin[xs]=0;
    bellman();
    afisare();
    return 0;
}
void citire()
{
    int i,x,y,m,c;
    fin>>n>>m;
    xs=1;
    for (i=0; i<m; i++)
    {
        fin>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
}
void afisare()
{
    int i;
    if (negativ==1) fout<<"Ciclu negativ!"<<'\n';
    else
    {
    for (i=2; i<=n; i++)
    {
        if (cmin[i]!=INFINIT) fout<<cmin[i]<<' ';
        else fout<<0<<' ';
    }
    fout<<'\n';
    }
}
void bellman()
{
    int i,x;
    c.push(xs);
    nr[xs]=1;
    while (!c.empty() && !negativ)
    {
        x=c.front();
        c.pop();
        for (i=0; i<G[x].size() && !negativ; i++)
        {
            if (cmin[x] + G[x][i].second<cmin[G[x][i].first])
            {
                cmin[G[x][i].first]=cmin[x] + G[x][i].second;
                prec[G[x][i].first]=x;
                c.push(G[x][i].first);
                nr[G[x][i].first]++;
                if (nr[G[x][i].first]>n-1) negativ=1;
            }

        }
    }

}