#include <cstdio>
#define INF 0x3f3f3f3f
using namespace std;

FILE *f;
FILE *g;

typedef struct nod
{
    int inf,c;
    nod *urm;
} NOD;
typedef NOD *graf[50010];
graf G;

NOD *C,*Cu,*p,*q;

int n,m,d[50010];
bool v[50010];
int cnt[50010];
void citire()
{
    f=fopen("bellmanford.in","r");
    fscanf(f,"%d %d",&n,&m);
    int a,b,c;
    for(int i=1;i<=m;i++)
    {
        fscanf(f,"%d %d %d",&a,&b,&c);
        p=new NOD;
        p->inf=b; p->urm=G[a]; p->c=c;
        G[a]=p;
    }
    fclose(f);
}

void init()
{
    for(int i=1;i<=n;i++)
        d[i]=INF;
    d[1]=0;
    C=new NOD;
    C->inf=1;
	cnt[1]=1;
    C->urm=NULL;
    Cu=C;
}



int main()
{
    citire();
    init();
	bool neg=false;
    while(C&&!neg)
    {
        p=G[C->inf];
        v[C->inf]=false;
        while(p&&!neg)
        {
            if(d[p->inf]>d[C->inf]+p->c)
				if(cnt[p->inf]>n)
					neg=true;
				else
				{
					d[p->inf]=d[C->inf]+p->c;
					if(!v[p->inf])
					{
						cnt[p->inf]++;
						q=new NOD;
						Cu->urm=q;
						q->inf=p->inf;
						q->urm=NULL;
						Cu=q;
						v[p->inf]=true;
					}
				}
            p=p->urm;
        }
        C=C->urm;
    }
    g=fopen("bellmanford.out","w");
	if(neg)
		fprintf(g,"Ciclu negativ!");
	else
    for(int i=2;i<=n;i++)
        fprintf(g,"%d ",d[i]<INF?d[i]:0);
    fprintf(g,"\n");
    fclose(g);
    return 0;
}