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