#include<fstream>
#include<deque>
#include<vector>
#define inf 200000005
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
struct muchie
{
    int y,c;
};
vector<muchie>a[50005];
deque<int>q;
int n,m,x,yy,cc,i,con[50005],d[50005];
bool ciclu;
muchie make_muchie(int &yy,int &cc)
{
    muchie rez;
    rez.y=yy;
    rez.c=cc;
    return rez;
}
void bell()
{
    int poz;
    for(i=1;i<=n;i++)
      d[i]=inf;
    d[1]=0;
    q.push_back(1);
    while(!q.empty()&&ciclu==0)
    {
        poz=q.front();
        q.pop_front();
        for(i=0;i<a[poz].size();i++)
          if(d[a[poz][i].y]>d[poz]+a[poz][i].c)
          {
             con[a[poz][i].y]++;
             if(con[a[poz][i].y]==n)
                ciclu=1;
             d[a[poz][i].y]=d[poz]+a[poz][i].c;
             q.push_back(a[poz][i].y);
          }
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>yy>>cc;
        a[x].push_back(make_muchie(yy,cc));
    }
    bell();
    if(ciclu==0)
      for(i=2;i<=n;i++)
        g<<d[i]<<" ";
    else
      g<<"Ciclu negativ!";
    return 0;
}