/// distanta de la nodul 1 la oricare nod dintr-un graf
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;
const int M = 25e4;
const int N = 5e4;
const int INF = 2e9;

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

vector<pair<int, int>> edges[N+1];
queue<int> q_node;
bitset <N+1> in_q ( false );
int cnt_in_cycle[N+1];
int dist[N+1];

int n, m;
void infinit_init () {
    for ( int i = 1; i <= n; i ++ )
       dist[i] = INF;
}

void ford () {

    q_node.push ( 1 ), dist[1] = 0, in_q[1] = true;
    bool negative_cycle = false;
    while ( !q_node.empty() && !negative_cycle ) {
       int x = q_node.front();
       in_q[x] = false;
       q_node.pop ();
       for ( int cnt_edge = 0; cnt_edge < (int)edges[x].size (); cnt_edge ++ )
          if ( dist[x] + edges[x][cnt_edge].second < dist[edges[x][cnt_edge].first] ) {
            dist[edges[x][cnt_edge].first] = dist[x] + edges[x][cnt_edge].second;

            if ( in_q[edges[x][cnt_edge].first] == false ) {
              if ( cnt_in_cycle[edges[x][cnt_edge].first] > n )
                negative_cycle = true;
              else {
                q_node.push ( edges[x][cnt_edge].first );
                cnt_in_cycle[edges[x][cnt_edge].first] ++;
                in_q[edges[x][cnt_edge].first] = true;
              }
            }
          }
    }

    if ( negative_cycle == true )
      fout << "Ciclu negativ!";
    else
      for ( int i = 2; i <= n; i ++ )
         fout << dist[i] << ' ';
}

int main()
{
   fin >> n >> m;
   for ( int i = 0; i < m; i ++ ) {
      int a, b, w;
      fin >> a >> b >> w;
      edges[a].push_back ( {b, w} );
   }

   infinit_init ();
   ford ();


    return 0;
}