#include <fstream>
#define INF 999999
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,m,c[9000][9000],d[9000];

void bellman(int x0)
{
    int i;
    for(i=1;i<=n;i++)
        d[i]=INF;
    d[x0]=0;
    int ok=0;
    for(i=1;i<=n;i++)
    {
        int j,k;
        ok=0;
        for(j=1;j<=n;j++)
            for(k=1;k<=n;k++)
            if(d[j]!=INF && c[j][k]!=INF)
            if(d[k]>d[j]+c[j][k])
            {
                d[k]=d[j]+c[j][k];
                ok=1;
            }
    }

    if(ok==1)
         fout <<"Ciclu negativ!";
    else
        for (i=2;i<=n;i++)
            fout<<d[i]<<' ';
}

int main()
{

    fin>>n>>m;
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        c[i][j]=INF;
    for(i=1;i<=m;i++)
    {
        int sa,sw,sd;
        fin>>sa>>sw>>sd;
        c[sa][sw]=sd;
    }
    bellman(1);

    return 0;
}