# include <iostream>
# include <fstream>
# include <vector>
# include <string.h>
# define nmax 5000
# define inf 1001
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int c[nmax][nmax];
int d[nmax], t[nmax], n, m;

int main()
{
    int i,x,y,z;
    f>>n>>m;
    memset(c,5,sizeof(c));

    for(i=1; i<=n; i++)
    {
        f>>x>>y>>z;
        c[x][y]=z;
    }

    for(i=1; i<=n; i++)
    {
        d[i]=c[0][0];
        t[i]=0;
    }

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

            }
    }

    if(ok==0)
        cout<<"Ciclu negativ!"<<'\n';
    else
    {
        for(i=2; i<=n; i++)
            g<<d[i]<<" ";
    }

    return 0;
}