//Bellman Ford

#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int INF = 1<<30;
const int MAXN = 50005;
vector < pair <int, int> > vecini[MAXN];
bool in_queue[MAXN];
vector <int> dist(MAXN, INF), cnt_in_queue(MAXN, 0);
int main()
{
    int i,m,n,x,y,c,neg_cycle=0;
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
     f>>x>>y>>c;
     vecini[x].push_back(make_pair(y,c));
    }
    queue <int> Q;
    dist[1]=0;
    Q.push(1);
    in_queue[1]=1;
    while(!Q.empty() && !neg_cycle)
    {
     x=Q.front();
     Q.pop();
     in_queue[x]=0;
     vector < pair <int, int> >::iterator it;
     for (it = vecini[x].begin(); it != vecini[x].end(); ++ it) 
      if (dist[x] < INF)
       if(dist[it->first]>dist[x]+it->second)
       {
        dist[it->first]=dist[x]+it->second;
        if(!in_queue[it->first])
        {
         if(cnt_in_queue[it->first] > n)
          neg_cycle=1;
         else
         {
             Q.push(it->first);
             in_queue[it->first]=1;
             cnt_in_queue[it->first]++;
         }
        }
       }
    }
    if(!neg_cycle)
    {
     for(i=2;i<=n;i++)
      g<<dist[i]<<" ";
     g<<"\n";
    }
    else 
     g<<"Ciclu negativ!\n";
    f.close();
    g.close();
    return 0;
}