#include<fstream>
#define in 1<<20
#define nmax 50005

using namespace std;

int n,m;
int c[nmax],d[nmax],v[nmax],uz[nmax];

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

struct lista
{
    int inf,c;
    lista *nod;
} *g[nmax];

void add(int i,int j,int k)
{
    lista *p;
    p=new lista;
    p->inf=j;
    p->c=k;
    p->nod=g[i];
    g[i]=p;
}

int ciclu()
{
    int i,nod,st,dr;
    lista *p;
    //memset(v,1,sizeof(v));
    //memset(d,in,sizeof(d));
    for(i=1;i<=n;++i)
        d[i]=in;
    st=dr=1;
    d[st]=0;
    uz[st]=1;
    v[st]=1;
    c[st]=1;
    while(st<=dr)
    {
        nod=c[st];
        v[nod]=0;
        for(p=g[nod];p;p=p->nod)
            if(d[p->inf]>d[nod]+(p->c))
            {
                d[p->inf]=d[nod]+(p->c);
                if(!v[p->inf])
                {
                    v[p->inf]=1;
                    c[++dr]=p->inf;
                    ++uz[p->inf];
                    if(uz[p->inf]>n)
                        return 1;
                }
            }
        ++st;
    }
    return 0;
}

int main()
{
    lista *p;
    int i,x,y,c;
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>x>>y>>c;
        add(x,y,c);
    }
    if(ciclu())
        fout<<"Ciclu negativ!\n";
    else
        for(i=2;i<=n;++i)
            if(d[i]==in)
                fout<<0<<" ";
            else
                fout<<d[i]<<" ";
    fout<<"\n";
    return 0;
}