#include <iostream>
#include <list>
#include <fstream>
#include <stack>
#include <vector>
#include <climits>

using namespace std;

// ifstream fin("input.txt");
// ofstream fout("output.txt");

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


class graf {
private:
    int n;
    bool este_orientat;
    bool muchiile_au_cost;
    list<int> *ad;
    list<int> *cost;

public:
    graf(int n=1, bool o=1, bool c=0) {
        this->n = n;
        this->este_orientat = o;
        this->muchiile_au_cost = c;
        this->ad = new list<int>[n];
        this->cost = new list<int>[n];
    };

    void adaug_muchie(int v, int w, int cst=INT_MAX) {
        if (este_orientat == 1) {
            this->ad[v].push_back(w);

            if (muchiile_au_cost)
                this->cost[v].push_back(cst);
        }  
        else {
            this->ad[v].push_back(w);
            this->ad[w].push_back(v);

            if (muchiile_au_cost) {
                this->cost[v].push_back(cst);
                this->cost[w].push_back(cst);
            }
        }
    };

    void BFS(int s);
    void distante(int s);

    void DFS(int s);
    void DFS_recursiv(int s, bool *vizitat);
    int nr_conexe();

    int* sortaret();
    void dfs_top(int &ind, int i, bool* vizitat, int* sortare);

    int* bellman_ford();
};

void graf::BFS(int s) {
    bool *vizitat = new bool[n];
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
    }

    list<int> coada;
    vizitat[s] = true;
    coada.push_back(s);

    while(!coada.empty()) {
        list<int>::iterator i;

        s = coada.front();
        fout << s << " ";
        // fout << s+1 << " ";

        coada.pop_front();

        for (i = ad[s].begin(); i != ad[s].end(); i++) {
            if (vizitat[*i] == false) {
                vizitat[*i] = true;
                coada.push_back(*i);
            }
        }
    }
    delete[] vizitat;
}

void graf::distante(int s) {
    bool *vizitat = new bool[n];
    int *distante = new int[n];
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
        distante[i] = -1;
    }

    list<int> coada;
    vizitat[s] = true;
    coada.push_back(s);
    distante[s] = 0;

    while(!coada.empty()) {
        list<int>::iterator i;

        s = coada.front();
        coada.pop_front();

        for (i = ad[s].begin(); i != ad[s].end(); i++) {
            if (vizitat[*i] == false) {
                vizitat[*i] = true;
                distante[*i] = distante[s] + 1;
                coada.push_back(*i);
            }
        }
    }

    for (int i = 0; i < n; i++) {
        fout << distante[i] << " ";
    }

    delete[] vizitat;
    delete[] distante;
}

void graf::DFS(int s) {
    bool *vizitat = new bool[n];
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
    }

    DFS_recursiv(s, vizitat);
    delete[] vizitat;
}

void graf::DFS_recursiv(int s, bool *vizitat) {
    vizitat[s] = true;
    // fout << s << " ";

    list<int>::iterator it;

    for (it = ad[s].begin(); it != ad[s].end(); it++) {
        if (!vizitat[*it])
            DFS_recursiv(*it, vizitat);
    }
}

int graf::nr_conexe() {
    bool *vizitat = new bool[n];
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
    }
    int nr = 0;

    for (int i = 0; i < n; i++) {
        if (!vizitat[i]) {
            DFS_recursiv(i, vizitat);
            nr ++;
        }
    }

    delete[] vizitat;
    return nr;
}

int* graf::sortaret() {
    bool *vizitat = new bool[n];
    int *sortare = new int[n];
    for (int i = 0; i < n; i++) {
        vizitat[i] = false;
        sortare[i] = -1;
    }

    int ind = n - 1;

    for (int i = 0; i < n; i++) {
        if (!vizitat[i]) {
            dfs_top(ind, i, vizitat, sortare);
        }
    }

    delete[] vizitat;
    return sortare;
}

void graf::dfs_top (int &ind, int i, bool* vizitat, int* sortare) {
    vizitat[i] = true;

    list<int>::iterator it;

    for (it = ad[i].begin(); it != ad[i].end(); it++) {
        if (!vizitat[*it]) {
            dfs_top(ind, *it, vizitat, sortare);
        }
    }


    sortare[ind] = i;
    ind --;
}

int* graf::bellman_ford() {
    int* distante = new int[n];
    distante[0] = 0;
    for (int i = 1; i < n; i++) {
        distante[i] = INT_MAX;
    }
    int contor = 0;

    for (int i = 0; i < n-1; i++) {
        for (int nod = 0; nod < n; nod++) {
            list<int>::iterator it, cst = cost[nod].begin();

            for (it = ad[nod].begin(); it != ad[nod].end(); it++) {
                if (distante[nod] + (*cst) < distante[*it]) {
                    distante[*it] = distante[nod] + (*cst);
                    contor = 1;
                }
                cst++; 
            }
        }
        if (contor == 0) // daca deja am ajuns la distantele minime
            break;
        else contor = 0;
    }

    for (int nod = 0; nod < n; nod++) {
            list<int>::iterator it, cst = cost[nod].begin();

            for (it = ad[nod].begin(); it != ad[nod].end(); it++) {
                if (distante[nod] + (*cst) < distante[*it]) {
                    fout << "Ciclu negativ!";
                    return NULL;
                }
                cst++; 
            }
        }

    return distante;
}

int main() {
    int n, m, a, b, c;
    fin >> n >> m;
    graf g(n, 1, 1);

    for (int i = 0; i < m; i++) {
        fin >> a >> b >> c;
        g.adaug_muchie(a-1, b-1, c);
    }

    int* p = g.bellman_ford();
    for (int i = 0; i < n; i++) {
        fout << p[i] << " ";
    }
    delete[] p;
    return 0;
}