#include <iostream>
#include <fstream>
#include <queue>
#define nmax 50005
#define mmax 250005
#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 )
          {
              d[ v[q.front()][i].first ] = min( d[ v[q.front()][i].first ], d[q.front()] + v[ q.front() ][i].second );
              q.push( v[ q.front() ][i].first );


          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]<<" ";




}