#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

#define MAX_N 50000
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

struct muchie{
    int nod, cost;
};

vector<muchie> vec[MAX_N]; // lista de adiacenta
long n, m;
queue<long> coada; // coda in care am nodurile
bool in_coada[MAX_N]; // vector in care retin daca nodul se afla sau nu in coda
long nr_vizitari[MAX_N]; // vector in care retin de cate ori am trecut prin nodul i; daca valoare e mai mare ca n , atunci am ciclu negativ
void bellmanford();

int main()
{
    fin >> n >> m;
    for(long i=1; i<=m; i++){
        long x; muchie m;
        fin >> x, fin >> m.nod >> m.cost;
        vec[x].push_back(m);
    }

    bellmanford();

    return 0;
}


void bellmanford(){
    long drum[MAX_N];
    drum[1] = 0;
    for(long i=2; i<=n; i++)
        drum[i] = MAX_N;


    coada.push(1), in_coada[1] = true;

    while(!coada.empty()){
        long curent = coada.front();
        in_coada[curent] = false;
        coada.pop();

        for(size_t i=0; i<vec[curent].size(); i++){
            long destinatie = vec[curent][i].nod;
            long cost = vec[curent][i].cost;

            if(drum[destinatie] > drum[curent] + cost ){
                drum[destinatie] = drum[curent] + cost;
                if(!in_coada[destinatie]){
                    if(nr_vizitari[destinatie] > n){
                        fout << "Ciclu negativ!"; return;
                    }
                    coada.push(destinatie);
                    in_coada[destinatie] = true;
                    nr_vizitari[destinatie]++;
                }

            }

        }

    }

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