#include <bits/stdc++.h>
using namespace std;

vector<vector<pair<int, int>>> graph;
int n, m;

vector<int> dist;
vector<bool> inQueue;

struct comp{
    bool operator()(int a, int b){
        return dist.at(a) > dist.at(b);
    }
};

priority_queue<int, vector<int>, comp> pQueue;
vector<int> queueCont;

bool dijkstra(){
    dist.resize(n+1, INT_MAX);
    inQueue.resize(n+1, false);
    queueCont.resize(n+1, 0);

    dist.at(1) = 0;
    pQueue.push(1);


    while(!pQueue.empty()){
        int current = pQueue.top();
        pQueue.pop();
        inQueue.at(current) = false;
        for(auto& elem:graph.at(current)){
            if(dist.at(elem.first)>dist.at(current)+elem.second){
                dist.at(elem.first) = dist.at(current) + elem.second;
                queueCont.at(elem.first)++;

                if(inQueue.at(elem.first)==false){
                    if(queueCont.at(elem.first) >n) return false;
                    inQueue.at(elem.first) = true;
                    pQueue.push(elem.first);

                }
            }
        }
    }
    return true;

}
int main()
{
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");

    fin>>n>>m;

    int x, y, c;

    graph.resize(n+1, vector<pair<int, int>>());

    for(int i=1; i<=m; i++){
        fin>>x>>y>>c;
        graph.at(x).push_back(make_pair(y, c));
    }

    if(dijkstra() == false){
        fout<<"Ciclu negativ!";
        return 0;
    }

    for(int i=2; i<=n; i++)
        fout<<dist.at(i)<<" ";
}