#include<fstream>
#include<deque>
#include<vector>
#define inf 1<<30
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)//construieste muchia:pentru nodul x adaug nodul de care se leaga(y) cu costul 'c'
{
    muchie rez;
    rez.y=yy;
    rez.c=cc;
    return rez;
}
void bell()
{
    int poz;
    for(i=1;i<=n;i++)//initializam vectorul pentru distante
      d[i]=inf;
    d[1]=0;
    q.push_back(1);//adaugam nodul de pornire, pentru care am setat distanta 0
    while(!q.empty()&&ciclu==0)
    {
        poz=q.front();//retin nodul de plecare
        q.pop_front();
        for(i=0;i<a[poz].size();i++)//iau fiecare nod adiacent
          if(d[a[poz][i].y]>d[poz]+a[poz][i].c)//daca pot imbunatati distanta
          {
             con[a[poz][i].y]++;//contorizam utilizarea nodului adiacent
             if(con[a[poz][i].y]==n)//daca nodul adiacent a fost folosit de n ori inseamna ca avem un ciclu
                ciclu=1;
             d[a[poz][i].y]=d[poz]+a[poz][i].c;//actualizez distanta
             q.push_back(a[poz][i].y);//adaug nodul adiacent in coada
          }
    }
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)//citesc muchiile
    {
        f>>x>>yy>>cc;
        a[x].push_back(make_muchie(yy,cc));
    }
    bell();
    if(ciclu==0)//nu am ciclu
      for(i=2;i<=n;i++)
        g<<d[i]<<" ";
    else//am ciclu
      g<<"Ciclu negativ!";
    return 0;
}