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

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

int n,m,dp[50005],cnt[50005];
bool fost[50005];
vector< pair<int,int> >vecini[50005];
queue< pair<int,int> > coada;

int main()
{
 f>>n>>m;
 for(int i=1;i<=m;i++)
 {
  int x,y,z;
  f>>x>>y>>z;
  vecini[x].push_back(make_pair(y,z));
 }
 for(int i=1;i<=n;i++) dp[i]=100000000;
 fost[1]=1;
 dp[1]=0;
 coada.push(make_pair(0,1));
 bool ciclu=0;

 while( !coada.empty()&&!ciclu )
 {
  int nod=coada.front().second;
  coada.pop();
  fost[nod]=0;
  for(int i=0;i<vecini[nod].size();i++)
  {
   int x=vecini[nod][i].first,cost=vecini[nod][i].second;
   if( dp[x]>dp[nod]+cost )
   {
    dp[x]=dp[nod]+cost;
    if(cnt[x]>n)
     ciclu=1;
    else
    if(!fost[x]){
     fost[x]=1;
     coada.push(make_pair(dp[x],x));
     cnt[x]++;
    }
   }
  }
 }
 if( ciclu) g<<"Ciclu negativ!\n";
 else
 for(int i=2;i<=n;i++) g<<dp[i]<<' ';
}