#include <iostream>
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
#define FIN "bellmanford.in"
#define FOUT "bellmanford.out"
#define MAXN 50005
#define oo ((1LL<<31)-1)

using namespace std;

int nodes,
    edges;

queue<int> Queue;

vector<pair<int,int>> Graph[MAXN];
bitset<MAXN> inQueue;
int countInQueue[MAXN];
int distMin[MAXN];

bool negative_cycle = false;

void readData() {

     int x,
         y,
         cost;

         ifstream fin(FIN);

         fin>>nodes>>edges;

         cout<<nodes<<" "<<edges;

         while(edges--) {

            fin>>x>>y>>cost;

            Graph[x].push_back({y, cost});

         }

         fin.close();
}

void BellmanFord() {

    for(int i = 2; i <= nodes; ++i) distMin[i] = oo;

    distMin[ 1 ] = 0;

    Queue.push(1);

    inQueue[ 1 ] = true;

    while(!Queue.empty() && !negative_cycle) {

          int node = Queue.front();

          Queue.pop();

          for(auto it: Graph[ node ]) {

                 if(distMin[ it.first ] > distMin[ node ] + it.second) {

                    distMin[ it.first ] = distMin[ node ] + it.second;

                    if(!inQueue[it.first]) {

                          if(countInQueue[it.first] > nodes)  {

                             negative_cycle = true;

                          } else {

                               Queue.push( it.first );

                               inQueue[it.first] = true;

                               countInQueue[it.first]++;
                          }
                    }

                 }
          }

    }

}

void writeData() {

     ofstream fout( FOUT );

     if( negative_cycle ) {

         fout<<"Ciclu negative!";

     } else {

        for(int i = 2; i <= nodes; ++i) fout<<distMin[i] << " ";
     }

     fout.close();

}

int main(int argc, char const *argv[]) {

   readData();

   BellmanFord();

   writeData();

  return 0;
}