#include <iostream>
#include <fstream>
#define inf 2147000000
#include <vector>
#include <queue>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector <int> v[50005],c[50005];
queue <int> q;
 int n,m,cmin[50005],ap[50005],nod;
int main()
{ int i,x,y,cst,cost,nod,nod2,ok=0;
    f>>n>>m;
    for(i=1;i<=m;i++)
    { f>>x>>y>>cst;
      v[x].push_back(y);
      c[x].push_back(cst);
      cmin[i]=inf;
    }

    cmin[1]=0;
    q.push(1);
    ap[1]=1;
    while(!q.empty())
    { nod=q.front(); q.pop();

      for(i=0;i<v[nod].size();i++)
      { nod2=v[nod][i]; cost=c[nod][i];

        if (cmin[nod]+cost<cmin[nod2])
          {cmin[nod2]=cmin[nod]+cost;
           q.push(nod2); ap[nod2]++;
           if (ap[nod2]>n) {ok=1; break;}
          }
      }
     if (ok) break;
    }

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

    return 0;
}