#include <bits/stdc++.h>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
vector < pair < int,int > > v[50005];
int dist[50005];
int viz[50005];
queue < int > Q;
int n,m;
void read()
{
     in >> n >> m;
     int a,b,c;
     for(int i=1; i<=m; i++)
     {
         in >> a >> b >> c;
         v[a].push_back( { b,c } );
     }
     for(int i=2; i<=n; i++)
       dist[i] = INT_MAX;
     dist[1] =0;
}

int main()
{
     read();

 Q.push(1);
     while( !Q.empty() )
     {
          int head = Q.front();
          Q.pop();
          viz[head] ++ ;
          if( viz[head] == n )
          {
               out << "Ciclu negativ!";
               return 0;
          }
          m = v[head].size();
          for(int i=0; i<m; i++)
          {
               int j = v[head].at(i).first;
               int k = v[head].at(i).second;
               if( dist[j] > dist[head] + k)
               {
                    dist[j] = dist[head]+k;
                    Q.push(j);
               }
          }
     }
for(int i=2; i<=n; i++)
     out << dist[i] <<' ';

    return 0;
}