#include<stdio.h>
#include<limits.h>
#include<vector>
#include<queue>
using namespace std;
#define nrn 50005
#define inf INT_MAX

struct node{int nr,val;};
vector<node>V[nrn];
queue<int>Q;
int D[nrn],n,viz[nrn];

FILE *in=fopen("bellmanford.in","r"),*out=fopen("bellmanford.out","w");

int main()
{
    int i,m,a,b,c,pas;
    bool cnegativ=false;
    node p;

    fscanf(in,"%d %d",&n,&m);
    for(i=1;i<=m;++i)
    {
        fscanf(in,"%d %d %d",&a,&b,&c);
        p.nr=b;
        p.val=c;
        V[a].push_back(p);
    }
    for(i=1;i<=n;++i)
        D[i]=inf;
    Q.push(1);
    D[1]=0;
    viz[1]=1;
    while(!Q.empty()&&!cnegativ)
    {
        pas=Q.front();
        Q.pop();
        for(i=0;i<(int)V[pas].size();++i)
        {
            p=V[pas][i];
            if(D[p.nr]>p.val+D[pas])
            {
                D[p.nr]=p.val+D[pas];
                Q.push(p.nr);
                if(viz[p.nr]>n)//((int)Q.size()>n)
                    cnegativ=true;
                viz[i]++;
            }
        }
    }
    if(cnegativ)
        fprintf(out,"Ciclu negativ!\n");
    else for(i=2;i<=n;++i)
        fprintf(out,"%d ",D[i]);
    return 0;
}