#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>

#define oo 999999999

using namespace std;

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

struct graf
{
    int x;
    int y;
    int d;
} a[250005];

graf aux;

int n, m, viz[50005], k; // viz pt valoarea muchiilor

void bellf()
{
    int i, j;

    for (i=1; i<=n; i++)
      for (j=1; j<=m; j++)
        if (viz[a[j].x]+a[j].d<viz[a[j].y])
          viz[a[j].y]=viz[a[j].x]+a[j].d;
}

long negativ()
{
    long i;
    for (i=1; i<=m; i++)
      if (viz[a[i].x]+a[i].d<viz[a[i].y]) return 1;
    return 0;
}

int main()
{
    int i, j;

    f>>n>>m;
    for (i=1; i<=m; i++)
    {
        f>>a[i].x>>a[i].y>>a[i].d;
        //f>>aux.x>>aux.y>>aux.d; a[i].push_back(aux);
    }

    //memset(viz, oo, sizeof(viz)); viz[1]=0;
    for (i=2; i<=n; i++) viz[i]=oo; viz[1]=0;
    //for (i=1; i<=n; i++) cout<<viz[i]<<" ";

    bellf();

    if (negativ()) g<<"Ciclu negativ!"<<"\n";
     else
     {
         for (i=2; i<=n; i++) g<<viz[i]<<" ";
     }

    return 0;
}