#include <stdio.h>

using namespace std;

const int N=50001;
const int M=250001;
const int NIL=-1;
const int INF=1000000000;

struct nod
{
    int val;
    int urm;
    int cost;
};

nod a[2*M];
int q[N],ap[N],list[N],s[N],nr=0,p,u,n,m;
bool inq[N];

int main()
{
    FILE *in,*out;
    in=fopen("bellmanford.in","r");
    out=fopen("bellmanford.out","w");
    int i,x,y,poz,c;
    fscanf(in,"%d%d",&n,&m);
    for(i=1;i<=n;i++) {list[i]=NIL; s[i]=INF; inq[i]=0; ap[i]=0;}
    for(i=1;i<=m;i++)
    {
        fscanf(in,"%d%d%d",&x,&y,&c);
        a[nr].val=y;
        a[nr].urm=list[x];
        list[x]=nr;
        a[nr].cost=c;
        nr++;
    }
    q[0]=1;
    inq[1]=1;
    s[1] = 0;
    p=0; u=1;
    while(p!=u)
    {
        x=q[p];
        inq[x]=0;
        p=(p+1)%n;
        poz=list[x];
        while(poz!=NIL)
        {
            y=a[poz].val;
            if(s[x] + a[poz].cost < s[y])
            {
                s[y] = s[x] + a[poz].cost;
                if(inq[y]==0)
                {
                    inq[y]=1;
                    q[u]=y;
                    u=(u+1)%n;
                }
                ap[y]++;
                if(ap[y]>=n)
                {
                    fprintf(out,"Ciclu negativ!");
                    return 0;
                }
            }
            poz=a[poz].urm;
        }
    }
    for(i=2;i<=n;i++) fprintf(out,"%d ",s[i]);
    return 0;
}