#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

class graf {

protected:
    int noduri, muchii;
    vector < vector < int >> adiacenta;

public:
    // Constructor cu matrice de adiacenta data
    graf(vector < vector < int >> listaAdiacenta, int noduri, int muchii): adiacenta(listaAdiacenta), noduri(noduri), muchii(muchii) {};

    // Constructor fara matrice de adiacenta, se cu initalizeaza una goala
    graf(int noduri, int muchii): adiacenta(noduri + 1), noduri(noduri), muchii(muchii) {};

    vector < int > bfs(int);
    int dfs();

};

class graf_neorientat : public graf{
private:
    void dfsbiconex(int, vector < int >&, vector < int >&, stack < pair < int, int >>&, int&, vector < string >&);
    void dfsCriticalConnections(int tata, vector < int >&, vector < int >&, int&, vector < vector < int >>&, vector < int >&);

public:
    graf_neorientat(vector < vector < int >> listaAdiacenta, int noduri, int muchii): graf(listaAdiacenta, noduri, muchii) {};
    graf_neorientat(int noduri, int muchii): graf(noduri, muchii) {};

    friend istream& operator>>(istream&, graf_neorientat&);

    vector < string > biconex();

    vector < vector < int >> criticalConnections();
};

class graf_neorientat_ponderat : public graf_neorientat {
    // Matrice de adianceta care contine si costurile
    vector< vector< pair< int, int >>> adiacentap;
public:
    graf_neorientat_ponderat(vector < vector < pair<int, int> >> listaAdiacenta, int noduri, int muchii): adiacentap(listaAdiacenta), graf_neorientat(noduri, muchii) {};
    graf_neorientat_ponderat(int noduri, int muchii): adiacentap(noduri+1), graf_neorientat(noduri, muchii) {};

    friend istream& operator>>(istream&, graf_neorientat_ponderat&);

    unordered_map<int, int> bellmanford();

};

istream& operator>>(istream& in, graf_neorientat_ponderat& g) {
    for (int i = 0; i < g.muchii; i++) {
        int aux1, aux2, aux3;
        in >> aux1 >> aux2 >> aux3;
        g.adiacentap[aux1].push_back(make_pair(aux2, aux3));
    }
    return in;
}

unordered_map<int, int> graf_neorientat_ponderat :: bellmanford() {
    unordered_map<int, int> m;
    queue<int> q;
    vector<int> cnt(noduri+1);
    unordered_set<int> check;

    m[1] = 0;
    q.push(1);
    check.insert(1);
    while(!q.empty()){
        int nod1 = q.front();
        check.erase(nod1);
        q.pop();

        for(pair<int, int> muchie : adiacentap[nod1]){
            int nod2 = muchie.first, cost = muchie.second;
            if(m.find(nod2) == m.end() || m[nod2] > m[nod1] + cost){
                m[nod2] = m[nod1] + cost;
                if(check.find(nod2) == check.end()){
                    q.push(nod2);
                    check.insert(nod2);
                    cnt[nod2]++;
                    if(cnt[nod2] > noduri){
                        m.clear();
                        return m;
                    }
                }
            }
        }
    }
    return m;
}

void bellmanfordDriver() {
    // https://infoarena.ro/problema/dijkstra
    // Citire
    ifstream in ("bellmanford.in");
    ofstream out("bellmanford.out");

    int n, m;
    in >> n >> m;

    vector<vector<pair<int, int>>> muchii(n+1);
    for(int i = 0; i < m; i++){
        int aux1, aux2, aux3;
        in >> aux1 >> aux2 >> aux3;
        muchii[aux1].push_back(make_pair(aux2, aux3));
    }

    graf_neorientat_ponderat x(muchii, n, m);

    unordered_map<int, int> v = x.bellmanford();
    if(v.empty()){
        out<<"Ciclu negativ!";
    }
    else{
        for(int i=2; i<=n; i++){
            out<<v[i]<<" ";
        }
    }

}

int main() {
    // Se apeleaza functia corespunzatoare problemei
    bellmanfordDriver();
    return 0;
}