#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

const int NMax = 5e4 + 2, Inf = 2e9;
int N, M, NrQ[NMax], Drum[NMax], Ok = 1;
vector < pair <int, int> > G[NMax];
queue <int> Q;
bool InQ [NMax];

void Read (){
    int x, y, k;
    in >> N >> M;
    while (M--){
        in >> x >> y >> k;
        G[x].push_back (make_pair(y, k));
    }
}

void Bellmanford (int Nod){
    Q.push(Nod);
    InQ[Nod] = true;
    NrQ[Nod] = 1;
    for (int i = 2; i <= N; ++i)
        Drum[i] = Inf;
    while (!Q.empty() && Ok){
        int Node = Q.front();
        Q.pop();
        InQ[Node] = false;
        for (int i = 0; i < (int)G[Node].size(); ++i){
            int Vecin = G[Node][i].first;
            int Cost = G[Node][i].second;
            if (Drum[Vecin] > Drum[Node] + Cost){
                Drum[Vecin] = Drum[Node] + Cost;
                if (!InQ[Vecin]){
                    Q.push(Vecin);
                    InQ[Vecin] = true;
                    NrQ[Vecin]++;
                    if (NrQ[Vecin] > N)
                        Ok = 0;
                }
            }
        }
    }
}

void Write(){
    if (!Ok)
        out << "Ciclu negativ!\n";
    else
        for (int i = 2; i <= N; ++i)
            out << Drum[i] * (Drum[i] != Inf) << " ";
}

int main(){
    Read();
    Bellmanford(1);
    Write();
    return 0;
}