#include<fstream>
#include<vector>
using namespace std;
#define inn 1<<30
#define nn 50005
struct nod
{
    int vf,val;
    nod *next;
};
nod *g[nn];
int v[nn], d[nn],n,apar[nn];
void adauga(int a,int b,int c)
{
    nod *p=new nod;
    p->vf=b;
    p->val=c;
    p->next=g[a];
    g[a]=p;
}
int bmf(int sursa)
{
    vector<int> coada;
    int st,dr;
    coada.push_back(sursa);
    st=dr=0;
    v[sursa]=1;
    d[sursa]=0;
    while(st<=dr)
    {
        int k=coada[st];
        v[k]=0;
        st++;
        if(d[k]<inn)
        for(nod *p=g[k] ; p ; p=p->next)
        {
            int kk=p->vf;
            if(d[kk]>d[k]+p->val)
            {
                d[kk]=d[k]+p->val;
                if(v[kk]==0)
                {
                    if(apar[kk]>n)
                      return 1;
                    v[kk]=1;
                    apar[kk]++;
                    coada.push_back(kk);
                    dr++;
                }
            }
        }
    }
    return 0;
}

int main()
{
    int m,i;
    ifstream fin("bellmanford.in");
    FILE *f=fopen("bellmanford.out","w");
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        int a,b,c;
        fin>>a>>b>>c;
        adauga(a,b,c);
    }
    for(i=1;i<=n;i++)
        d[i]=inn,v[i]=0;
    if(bmf(1))
		fprintf(f,"Ciclu negativ!");
	else
    for(i=2;i<=n;i++)
    {
        if(d[i]==inn)
            fprintf(f,"0 ");
        else
            fprintf(f,"%d ", d[i]);
    }
    return 0;
}