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

using namespace std;

#define MAX_N 500000
#define INF 1001
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] = INF;


    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++){
            if(drum[vec[curent][i].nod] > drum[curent] + vec[curent][i].cost ){
                drum[vec[curent][i].nod] = drum[curent] + vec[curent][i].cost;
                if(!in_coada[vec[curent][i].nod]){
                    if(nr_vizitari[vec[curent][i].nod] > n){
                        fout << "Ciclu negativ!"; return;
                    }
                    coada.push(vec[curent][i].nod);
                    in_coada[vec[curent][i].nod] = true;
                    nr_vizitari[vec[curent][i].nod]++;
                }

            }

        }

    }

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


}