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

using namespace std;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

const int NMAX = 50005;
const int oo = 1000 * NMAX * 5;
vector <pair<int, int> > G[NMAX];
queue <int> q;
int N, M, D[NMAX], no_queue[NMAX];
bool in_queue[NMAX], invalid_graph;

void Read(){
    in >> N >> M;
    for(int i = 1; i <= M; ++i){
        int a, b, c;
        in >> a >> b >> c;
        G[a].push_back(make_pair(b, c));
    }
}

void Init(){
    for(int i = 2; i <= N; ++i)
        D[i] = oo;
}

void Solve(){
    q.push(1);
    in_queue[1] = true;
    no_queue[1] = 1;
    while(!q.empty() && !invalid_graph){
        int node = q.front();
        q.pop();
        in_queue[node] = false;
        for(int i = 0; i < G[node].size(); ++i){
            int neighbour = G[node][i].first;
            int neighbour_edge_weight = G[node][i].second;
            if(D[neighbour] > D[node] + neighbour_edge_weight){
                D[neighbour] = D[node] + neighbour_edge_weight;
                if(!in_queue[neighbour]){
                    q.push(neighbour);
                    no_queue[neighbour]++;
                    if(no_queue[neighbour] > N - 1){
                        invalid_graph = true;
                        return;
                    }
                }
            }
        }
    }
}

void Print(){
    if(invalid_graph)
        out << "Ciclu negativ!";
    else
        for(int i = 2; i <= N; ++i)
            out << D[i] * (D[i] != oo) << " ";
    out << "\n";
}

int main(){
    Read();
    Init();
    Solve();
    Print();
    return 0;
}