#include <bits/stdc++.h>
#define nmax 50005
#define inf 100000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m;
int d[nmax],nr[nmax];
bool negativ;
vector <pair<int,int> > G[nmax];
queue <int> C;

void read()
{int i,x,y,z;
 f>>n>>m;
 for(i=1;i<=m;i++)
   {f>>x>>y>>z;
    G[x].push_back(make_pair(y,z));
   }
}

void bellmanford()
{int i,x;
 vector <pair<int,int> > ::iterator it;
 for(i=1;i<=n;i++) d[i]=inf;
 d[1]=0;
 C.push(1);
 while(!C.empty()&&!negativ)
 {x=C.front(); C.pop();
  for(it=G[x].begin();it!=G[x].end();++it)
    if(d[it->first]>d[x]+it->second)
     {d[it->first]=d[x]+it->second;
      nr[it->first]++;
      C.push(it->first);
      if(nr[it->first]>n) {negativ=true; return;}
    }
 }
}

void write()
{if(negativ) g<<"Ciclu negativ!\n";
 else
 {for(int i=2;i<=n;i++)
     g<<d[i]<<" ";
  g<<"\n";
  }
}

int main()
{read();
 bellmanford();
 write();
 return 0;
}