#include <stdio.h>
#include <algorithm>
#define INF 10000000
#define Nmax 50500

using namespace std;

int best[Nmax],coada[Nmax*10],nrviz[Nmax],viz[Nmax],dr=1,st,S=1,ai_ciclu_soro;
int n,m,x,y,z;
struct nod{
            int start,sf,cost;
            nod *next;
            };
nod *L[Nmax];
void add( int x, int y, int z)
{
    nod *q=new nod;
    q->start=x;
    q->sf=y;
    q->cost=z;
    q->next=L[x];
    L[x]=q;
}
void BellmanFord(int k)
{
    viz[k]=0;
    for(nod *p=L[k]; p!=NULL; p=p->next)
    {
        if(best[p->sf]>best[k]+p->cost)
        {
            best[p->sf]=best[k]+p->cost;

            if(viz[p->sf]==0)
            {
                viz[p->sf]=1;
                coada[dr++]=p->sf;
                nrviz[p->sf]++;
                if(nrviz[p->sf]==n+1)
                {
                    ai_ciclu_soro=1;
                    return;
                }
            }
        }
    }
}
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);

    scanf("%d%d",&n,&m);

    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d\n",&x,&y,&z);
        add(x,y,z);
    }
    for(int i=1; i<=n; ++i)
        best[i]=INF;

    coada[st]=S;
    viz[S]=1;
    nrviz[S]=1;
    best[S]=0;

    while(st<dr)
    {
        BellmanFord(coada[st]);
        if(ai_ciclu_soro==1)
        {
            printf("Ciclu negativ!");
            exit(0);
        }
        st++;
    }
    for(int i=2;i<=n;++i)
        printf("%d ",best[i]);
}