#include <cstdio>
#include <vector>
#include <queue>
#define Nmax 50005
#define INF 10000009
using namespace std;

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

int n,m,d[Nmax],ciclu[Nmax];
vector <int> G[Nmax],C[Nmax];
queue <int> q;

bool bellmanford()
{
    q.push(1);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        if(++ciclu[x]>n)
            return 0;
        for(int i=0; i<G[x].size(); i++)
            if(d[G[x][i]]>d[x]+C[x][i])
                {
                    d[G[x][i]]=d[x]+C[x][i];
                    q.push(G[x][i]);
                }
    }
    return 1;
}

int main()
{
    fscanf(in,"%d%d",&n,&m);
    for(int i=1; i<=m; i++)
    {
        int x,y,c;
        fscanf(in,"%d%d%d",&x,&y,&c);
        G[x].push_back(y);
        C[x].push_back(c);
    }
    for(int i=2;i<=n;i++)
        d[i]=INF;
    bool ok=bellmanford();
    if(ok==1)
        for(int i=2; i<=n; i++)
            fprintf(out,"%d ",d[i]);
    else fprintf(out,"Ciclu negativ!");
    return 0;
}