/* Bellman-Ford */
#include<fstream>
#include<queue>
#include<vector>
const int white=0;
const int gray=1;
const int black=2;
using namespace std;

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

int n,m,i,s,dist[50001],used[250001],ciclu,i_used;
struct muchie{int nod; int cost; int ind;};
vector<muchie> v[50001];



void bellman_ford(int origin)
{queue <int> q;
 int destination,cost_link;
 q.push(origin);
 while(!q.empty())
 {origin=q.front();
  q.pop(); 
  for(i=0; i<v[origin].size(); i++)
    {destination=v[origin][i].nod;
     cost_link=v[origin][i].cost;
     i_used=v[origin][i].ind;
     if(dist[destination]==0 || dist[destination]>dist[origin]+cost_link)
        {dist[destination]=dist[origin]+cost_link;
         used[i_used]++;
         if(used[i_used]==n)
            {ciclu=1; break;}
         q.push(destination);}
     }
      
  }
  
}

int main()
{f>>n>>m;
int a,b,c;
muchie x,y;
for(i=1; i<=m; i++)
{f>>a>>b>>c;
x.nod=b;  x.cost=c;   x.ind=i;
v[a].push_back(x);
}

s=1;

bellman_ford(s);

if(!ciclu)
for(i=2; i<=n; i++)
  g<<dist[i]<<" ";
else
 g<<"Ciclu negativ!";

f.close();
g.close();
return 0;}