#include <fstream>
#include <cstdlib>
#define inf 20005
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,c[1001][1001],d[25000],use[25000];
void citire()
{
    int l,a,b,i,j;
    f>>n>>m;
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            {if(i==j)c[i][j]=0;
            else c[i][j]=inf;
            }
    for(i=1; i<=m; i++)
    {
        f>>l>>a>>b;
        c[l][a]=b;
    }
}
void Dijkstra(int s)
{
    int k,min1,x,i,j;
    for(i=1; i<=n; i++)d[i]=inf;
    d[s]=0;
    for(k=1; k<=n; k++)
    {
        min1=inf;
        for(i=1; i<=n; i++)
            if(!use[i]&&d[i]<min1)
            {
                min1=d[i];
                x=i;
            }
        if(min1==inf) break;
        use[x]=1;
        for(i=1; i<=n; i++)
            if(d[x]+c[x][i]<d[i])
            {
                d[i]=d[x]+c[x][i];
            }
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        if(i!=j&&c[j][i]!=inf&&d[j]+c[j][i]<d[i]){g<<"Ciclu negativ";
                                                   exit(0);}
}

int main()
{
    citire();
    Dijkstra(1);
    for(int i=2; i<=n; i++)
        g<<d[i]<<" ";

    return 0;
}