#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 < int >> listaAdiacenta, int noduri, int muchii): graf_neorientat(listaAdiacenta, 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(vector<vector<int>>);

};

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(vector<vector<int>> muchii) {

    unordered_map<int, int> m;

    m[1] = 0;
    for(int i = 0; i < noduri - 1; i++){
        for(vector<int> muchie : muchii){
            int nod1 = muchie[0], nod2 = muchie[1], cost = muchie[2];
            if(m.find(nod1) != m.end() && (m.find(nod2) == m.end() || m[nod2] > m[nod1] + cost)){
                m[nod2] = m[nod1] + cost;
            }
        }
    }
    for(vector<int> muchie : muchii){
        int nod1 = muchie[0], nod2 = muchie[1], cost = muchie[2];
        if(m.find(nod1) != m.end() && m[nod2] > m[nod1] + cost){
            m.clear();
        }
    }
    return m;

}

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

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

    graf_neorientat_ponderat x(n, m);
    vector<vector<int>> muchii;
    for(int i = 0; i < m; i++){
        int aux1, aux2, aux3;
        in >> aux1 >> aux2 >> aux3;
        muchii.push_back({aux1, aux2, aux3});
    }

    unordered_map<int, int> v = x.bellmanford(muchii);
    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;
}