#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
#define MAX_N 50000

struct muchie{
    long x, y, cost;
};

vector<muchie> vec; // vector de muchii
long drum[MAX_N]; // vector de drumuri
long n, m, viz[MAX_N];

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

int main()
{


    fin >> n >> m;

    for(long i=1; i<=n; i++){
        drum[i] = MAX_N;
    }


    for(long i=0; i<m; i++){
        muchie m; fin >> m.x >> m.y >> m.cost;
        vec.push_back(m);
        if(m.x == 1)
            drum[m.y] = m.cost;
    }




    bellmanford(1);
    return 0;
}


void bellmanford(int nod){

    for(long j=1; j<=n-1; j++)
        for(size_t i=0; i< vec.size(); i++){
            if(drum[vec[i].y] > drum[vec[i].x] + vec[i].cost){
                drum[vec[i].y] = drum[vec[i].x] + vec[i].cost;
                viz[vec[i].y] ++;
                if(viz[vec[i].y]>=n-1){
                    fout << "Ciclu negativ!"; return;
                }
            }
        }

        for(long i=2; i<=n; i++){
          fout << drum[i] << " ";
        }

}