#include <bits/stdc++.h>
#define nmax 50005
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
vector < pair < int,int > > v[nmax];
queue < int > q;
int dist[nmax], viz[nmax], n, m;
void read()
{
     in >> n >> m ;
     int a,b,c;
     while(m--)
     {
          in >> a >> b >> c;
          v[a].push_back( { b,c } );
     }
     for(int i=2; i<=n; i++) dist[i] = INT_MAX;
}
int main()
{
     read();
     q.push(1);
     while ( !q.empty() )
     {
          int head = q.front();
          q.pop();
          viz[head]++;
          if( viz[head] == n) return out<< "Ciclu negativ!",0;
          for(int i=0; i<v[head].size(); i++)
          {
               int j = v[head][i].first;
               int cost = v[head][i].second;
               if( dist[j] > dist[head] + cost)
                   dist[j] = dist[head] + cost, q.push(j);
          }
     }

for(int i=2; i<=n; i++) out << dist[i] << ' ';
    return 0;
}