#include <iostream>
#include <fstream>
#include <queue>
#define nmax 50005
#define inf 0x3f3f3f
using namespace std;

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

int n, m;
vector< pair<int,int> > v[nmax];
queue<int> q;
vector<int> d(nmax, inf);

void citeste()
{ int x, y, c;

    in>>n>>m;
    for (int i=1; i<=m; ++i)
     {
         in>>x>>y>>c;
         v[x].push_back(make_pair(y,c));
     }
}

int bellmanford()
{
    d[1] = 0;
    q.push(1);
    while ( !q.empty() )
     {
         for ( unsigned i = 0; i < v[ q.front() ].size(); ++i )
          {
              if ( d[ v[ q.front() ][i].first ] > d[ q.front() ] + v[ q.front() ][i].second )
               {
                   d[ v[ q.front() ][i].first ] = d[ q.front() ] + v[ q.front() ][i].second;
                   q.push( v[ q.front() ][i].first );
               }

              else
                if ( d[ v[ q.front() ][i].first ] > 0 && d[ q.front() ] < 0 )
                    return 0;
          }
          q.pop();
     }
}

int main()
{
    citeste();

    if ( !bellmanford() )
     cout<<"Ciclu negativ!";
     else
      for (int i=2; i<=n; ++i)
       if ( d[i] == inf )
        out<<"0 ";
        else
         out<<d[i]<<" ";
return 0;
}