#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
 struct muchie
 { int nod,cost; };

 vector<muchie> v[50005];

  muchie el;

  queue <int> q;

  int n,m,dm[50005],use[50005],inq[50005],inf=0x3f3f3f3f,neg;
int main()
{ int i,x,y,z,c;
     f>>n>>m;

    for(i=1;i<=m;i++)
    {
      f>>x>>y>>z;
      el.nod=y; el.cost=z;
      v[x].push_back(el);
    }

    q.push(1); use[1]=1;
     dm[1]=0;

    for(i=2;i<=n;i++)
     dm[i]=inf;

    while(!q.empty())
    {
        x=q.front(); q.pop(); use[x]=0;
           // cout<<x<<"\n";
        for(i=0;i<v[x].size();i++)
        { y=v[x][i].nod; c=v[x][i].cost;
            if (dm[x]+c<dm[y])
             {
                dm[y]=dm[x]+c; inq[y]++;
               if (inq[y]==n) {neg=1;break;}
                if (!use[y]) {use[y]=1; q.push(y);}
             }
        }
      if (neg) break;
    }
  if (neg) g<<"Ciclu negativ!\n";
   else
    for(i=2;i<=n;i++)
     g<<dm[i]<<" ";
    return 0;
}