#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;

void bellmanford(int nod);
bool verifica_ciclu();

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;
    }

   bool exista =  verifica_ciclu();

    if(!exista){
        for(long i=2; i<=n; i++){
          fout << drum[i] << " ";
        }
    } else fout << "Ciclu negativ!";

}

bool verifica_ciclu(){
    for(size_t i=0; i<vec.size(); i++){
        if(drum[vec[i].y] > drum[vec[i].x] + vec[i].cost)
            return true;
    }

    return false;
}