#include <iostream>
#include <fstream>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int a[5001][5001]={0},n,m,inf=1999999999,i,j,k,b[5001][5001]={0};

int main()
{
    fin>>n>>m;

    b[1][1]=0;
    for(j=2;j<=n;j++)
        b[1][j]=inf;

    int x,y,val;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>val;
        a[x][y]=val;
        if(x==1)
            b[1][y]=val;
    }

    //for(i=1;i<=n;i++)
        //cout<<b[1][i]<<" ";

    int OK=1,numar=0;
    for(i=2;i<=n+2&&OK==1;i++)
    {
        OK=0;

        for(j=2;j<=n;j++)
        {
            b[i][j]=b[i-1][j];

            for(k=1;k<=n;k++)
               if(a[k][j]!=0)
                  if(b[i-1][k] + a[k][j] < b[i-1][j])
                     b[i][j] = a[k][j] + b[i-1][k], OK=1;
        }

        numar++;
    }

    if(numar>=n-1)
           fout<<"Ciclu negativ!";
    else
        for(j=2;j<=n;j++)
           fout<<b[i-1][j]<<" ";

    return 0;
}