#include <bits/stdc++.h>

using namespace std;
vector<pair<int,int>>vecin[50005];
queue<int>q;
int dist[50005];
int parcurs[50005];
int main()
{
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
   int n,m,x,y,z;
   cin>>n>>m;
   for(int i=0;i<m;i++)
   {
    cin>>x>>y>>z;
    vecin[x].push_back({y,z});

   }
   for(int i=2;i<=n;i++)
    dist[i]=10e9;
   q.push(1);
   bool ok=0;
   while(q.size()>0&&ok==0)
   {
       int curr=q.front();
       q.pop();
       for(auto x: vecin[curr])
       {
           if(dist[x.first]>dist[curr]+x.second)
           {
               dist[x.first]=dist[curr]+x.second;
               q.push(x.first);
               parcurs[x.first]++;
               if( parcurs[x.first]==n)
               {
                   ok=1;
                   break;
               }
           }
       }
   }
   if(ok==0)
    for(int i=2;i<=n;i++)
    cout<<dist[i]<<" ";
else
    cout<<"Ciclu negativ!";
    return 0;
}