#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>

#define MAX 100001
#define INF 0x3f3f3f3f

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



class Graf{
public:
    //date membre
    vector <int> A[MAX];    //liste de adiacenta
    vector <vector <pair<int, int>>> Ca ;      //lista de adiacenta cu costuri
    vector <pair<pair<int, int>, int> > Ac;     //vector de muchii cu costuri

    //noduri, muchii
    int mM, mN;

    //constructor

    Graf(int N, int M){
        mN = N;
        mM = M;
    }


    void BFS();

    void DFS(int start, vector<bool> &viz, stack<int> &S);
    void ComponenteConexe();


    void ComponenteBiconexe();
    void DFS_Biconex(int start, int father, vector <bool> &viz, vector <int> &up, vector <int> &nivel, stack <int> &S, int & nrComp, vector<vector<int>> &compBiconexe);
    void AfisareBiconex(int nrComp, vector<vector<int>> &compBiconexe);


    void ComponenteTareConexe();
    void DFST(const vector<vector<int>> &AT, int start, int comp, vector<bool> &viz, vector<vector<int>> &compTareConexe);

    void SortareTop();
//-----------------------------  drumuri minime si APM -----------------------------
    int Find(int x, vector <int> &parent);
    void Union(int x, int y, int &msol, vector <int> &parent, vector <int> &rank);
    void APM();

    void Disjoint();

    void Dijkstra(int start);

    void Bellman(int start);

};


void Graf :: BFS(){

    int x, y, start;
    fin >> start;
    for(int i = 1; i <= mM; i++){
        fin >> x >> y;
        A[x].push_back(y);
    }

    bool viz[MAX] = {false};
    queue <int> Q;

    int lg[MAX] = {0};  // lungimea drumului

    // vizitam nodul curent
    viz[start] = true;
    // il punem in coada
    Q.push(start);

    // fout<<1;
    while ( !Q.empty() ){
        x = Q.front();
        Q.pop();
        // preluam primul element din coada apoi il eliminam din coada

        for(int i = 0; i < A[x].size(); i++){
            // parcurgem toti vecinii lui x
            if(viz[A[x][i]] == 0){   // daca nu am mai vizitat vecinul asta{
                Q.push(A[x][i]);

                // il vizitam
                viz[A[x][i]] = 1;
                // creste lungimea drumului
                lg[A[x][i]] = lg[x] + 1;

            }
        }
    }

    for(int i = 1; i <= mN; i++)
        if(viz[i] != 0)
            fout << lg[i] << " ";
        else
            fout << -1 << " ";

}

void Graf::DFS(int start, vector<bool> &viz, stack<int> &S) {
    viz[start] = true;
    // vizitam nodul din care plecam

    for(int i = 0; i < A[start].size(); i++){
        // parcurgem toti vecinii nodului start
        if(!viz[A[start][i]] ){
            // daca nu am mai vizitat acest vecin
            DFS(A[start][i], viz, S);
        }
    }
    S.push(start);
}


void Graf::ComponenteConexe() {
    int x, y;
    stack <int> S;

    for(int i = 1; i <= mM; i++){
        fin >> x >> y;
        A[x].push_back(y);
        A[y].push_back(x);
    }

    vector<bool> viz(mN+1, false);
    int nrComp = 0;

    for(int i = 1; i <= mN; i++){
        if(!viz[i]){
            nrComp++;
            DFS(i,viz, S);
        }
    }

    fout << nrComp;

}

void Graf::DFS_Biconex(int start, int father, vector<bool> &viz, vector<int> &up, vector<int> &nivel, stack<int> &S,
                       int &nrComp, vector<vector<int>> &compBiconexe) {
    viz[start] = true;
    // vizitam nodul din care plecam
    up[start] = nivel[start];
    S.push(start); // adaugam startul in stiva

    for ( auto i : A[start] ){
        // parcurgem toti vecinii nodului start

        if ( i == father ) continue;

        //daca nu e nodul din care am venit
        if ( viz[i] ){
            // daca am mai vizitat acest vecin
            up[start] = min(up[start], nivel[i]);
        }
        else{

            nivel[i] = nivel[start] + 1;
            DFS_Biconex(i, start, viz, up, nivel, S, nrComp,compBiconexe);

            if ( up[i] >= nivel[start] ){

                nrComp++;
                while ( !S.empty() && S.top() != i ){
                    compBiconexe[nrComp].push_back(S.top());
                    S.pop();
                }
                compBiconexe[nrComp].push_back(S.top());
                S.pop();
                compBiconexe[nrComp].push_back(start);
            }
            up[start] = min(up[start], up[i]);
        }
    }
}

void Graf::AfisareBiconex(int nrComp, vector<vector<int>> &compBiconexe) {
    fout << nrComp << "\n";
    for ( int i = 1; i <= nrComp; i++ ){
        for ( auto j : compBiconexe[i] )
            fout << j << " ";
        fout << "\n";
    }
}

void Graf::ComponenteBiconexe() {
    int x, y;
    vector <vector<int>> compBiconexe(mN+1);
//    bool viz[MAX] = {false};
    vector <bool> viz(mN+1,0);
    int nrComp = 0;
//    int up[MAX] = {0};
    vector <int> up(mN+1, 0);
//    int nivel[MAX] = {0};
    vector <int> nivel(mN+1, 0);
//    int S[MAX] = {0};
    stack <int> S;

//    int top = 0;

    for(int i = 1; i <= mM; i++){
        fin >> x >> y;
        A[x].push_back(y);
        A[y].push_back(x);
    }

    DFS_Biconex(1,0, viz, up, nivel, S, nrComp, compBiconexe);
    AfisareBiconex(nrComp, compBiconexe);
}


void Graf::DFST(const vector<vector<int>>& AT, int start, int comp, vector<bool> &viz, vector<vector<int>> &compTareConexe) {

    viz[start] = true;
    // fout << 1;
    compTareConexe[comp].push_back(start);

//    for(int i = 0; i < AT[start].size(); i++){
    for(auto x : AT[start]){
        if(!viz[x] )
            DFST(AT, x, comp, viz, compTareConexe);
    }
}

void Graf::ComponenteTareConexe() {
    vector <bool> viz(mN+1, false);

    //graful transpus
    vector<vector<int>> AT(mN + 1);

    //componente tare conexe
    vector<vector<int>> compTareConexe(mN+1);

    //stiva
    stack<int> ST;

    //nr componente tare conexe
    int nrcomp = 0;

    int x, y;

    for(int i = 1; i <= mM; i++){
        fin >> x >> y;
        A[x].push_back(y);
        AT[y].push_back(x);
    }

    for(int i = 1; i <= mN; i++){
        if(!viz[i]){
            DFS(i, viz, ST);
        }
    }

    vector<bool> vizT(mN+1, false);

    //luam elementele in ordinea inversa a parcurgerii dfs
    //si aplicam dfs pe graful transpus
    while(!ST.empty()){
        x = ST.top();
        ST.pop();

        if(!vizT[x]){
            nrcomp ++;
            DFST(AT, x, nrcomp, vizT, compTareConexe);
        }
    }

    fout << nrcomp << "\n";

    for(int i = 1; i <= nrcomp; i++){
//        for(int j = 0; j < compTareConexe[i].size(); j++){
        for(auto x : compTareConexe[i]){
            fout << x << " ";
        }
        fout << "\n";
    }
}

void Graf::SortareTop() {

    int x, y;
    vector <bool> viz(mN+1, false);
    //stiva
    stack<int> ST;

    for(int i = 1; i <= mM; i++){
        fin >> x >> y;
        A[x].push_back(y);
    }

    for(int i = 1; i <= mN; i++){
        if(!viz[i]){
            DFS(i, viz, ST);
        }
    }

    while(!ST.empty()){
        fout << ST.top() << " ";
        ST.pop();
    }
}
// conditie de sortare
bool ok(const pair<pair<int, int>, int>&x, const pair<pair<int, int>, int>&y){
    //comparam al 2 lea parametru din perechile de tipul ((x,y),c) - care reprezinta costul
    return (x.second < y.second);
}


int Graf::Find(int x, vector<int> &parent) {
    //daca nu mai gasim tata pentru nodul curent
    if( x == parent[x])
        return x;

    //mergem din tata in tata pana gasim nodul de start
    parent[x] = Find(parent[x], parent);
    return parent[x];
}

void Graf::Union(int x, int y, int &msol, vector<int> &parent, vector<int> &rank) {
    //gasim radacina/stramosul fiecarei componente pe care vrem sa le unim
    int px = Find(x, parent);
    int py = Find(y, parent);

    if(rank[px] >= rank[py]){
        //parintele subarborelui mai mic devine subarborele mare (Radacina sa)

        parent[py] = px;
        rank[px] += rank[py];
        msol++;
    }
    else{

        parent[px] = py;
        rank[py] += rank[px];
        msol++;
    }
}

void Graf::APM() {

    vector<int> parent(mN+1);
    vector<int> rank(mN+1, 1);
    for (int i = 1; i <= mN; i++)
        parent[i] = i;

    int C = 0; //costul total
    //momentan n avem nicio muchie solutie
    int msol = 0;
    //muchiile solutie
    vector <pair<int, int> > sol;

    int x,y,c;

    for(int i = 0; i < mM; i++){

        fin >> x >> y >> c;
        Ac.push_back(make_pair(make_pair(x,y),c));

    }
    //sortam vectorul de muchii crescator in fc de cost
    sort(Ac.begin(), Ac.end(), ok);

    //verificam muchiile pe rand
    for(int i = 0 ; i < mM; i++){

        //cautam "cel mai indepartat stramos" pentru ambele capete ale muchiei
        x = Find(Ac[i].first.first, parent);
        y = Find(Ac[i].first.second, parent);
        //fout << Ac[i].first.first << " tatal: " << x << "\n";
        //fout << Ac[i].first.second << " tatal: " << y << "\n";

        //daca nu au "stramos" comun, atunci nu exista alt drum de la x la y in afara de muchia x-y
        if(y != x){
            //o adaugam in vect de sol
            sol.push_back(make_pair(Ac[i].first.first, Ac[i].first.second));

            //si punem muchia pe graful nostru actual
            Union(Ac[i].first.first, Ac[i].first.second, msol, parent, rank);

            //adunam costul muchiei la costul tota
            C+= Ac[i].second;
        }
    }

    fout << C << "\n";
    fout << msol <<"\n";

    for(int i = 0; i < msol; i++){
        fout << sol[i].first << " " << sol[i].second << "\n";

    }

}

void Graf::Disjoint() {
    int x,y,op;
    vector<int> parent(mN+1);
    vector<int> rank(mN+1, 1);

    //stiu ca n am nevoie de ele dar sa nu mai scriu alta functie de union, care in final face acelasi lucru
    int msol = 0;
    //muchiile solutie
    vector <pair<int, int> > sol;


    for (int i = 1; i <= mN; i++)
        parent[i] = i;

    for(int i = 0; i < mM; i++){

        fin >> op >> x >> y;
        if(op == 1){
            Union(x,y, msol, parent, rank);
        }
        else
        if(Find(x, parent) == Find(y, parent))
            fout << "DA\n";
        else
            fout << "NU\n";
    }
}

void Graf::Dijkstra(int start) {
    //vector pt drumurile minime
    vector<int> D(mN+1, INF);
    D[start] = 0;
    //multimea nodurilor pt care inca n am calculat durmul  minim
    vector <int> F(mN+1, 0);
    Ca.resize(mN+1);
    int x,y,c;

    for(int i = 0; i < mM; i++){

        fin >> x >> y >> c;
        Ca[x].push_back(make_pair(y,c));

    }

    priority_queue <pair<int, int>>q;
    q.push(make_pair(0,start));

    while (!q.empty())
    {
        int nod = q.top().second;
        q.pop();
        if (!F[nod] ){
            F[nod] = true;
            for (auto curr : Ca[nod])
            {
                if (D[nod] + curr.second < D[curr.first])
                {
                    D[curr.first] = D[nod] + curr.second;
                    q.push(make_pair(-D[curr.first], curr.first));
                }
            }
        }
    }
    for (int i = 2; i <= mN; i++)
        if (D[i] != INF)
            fout << D[i] << " ";
        else fout << 0 << " ";

}

void Graf::Bellman(int start) {

    Ca.resize(mN+1);
    int x,y,c;
    queue <int> C;
    vector <int> D(mN+1, INF);
    vector <int> viz(mN+1, 0);
    vector <bool> incoada(mN+1, 0);

    C.push(start);
    D[start] = 0; // distanta de la un nod la el insasi e 0
    incoada[start] = 1;


    bool ciclun = 0;

    for(int i = 0; i < mM; i++){

        fin >> x >> y >> c;
        Ca[x].push_back(make_pair(y,c));

    }
    while(!C.empty() && !ciclun){
        //fout << 1;
        int nod;
        nod = C.front();
        C.pop();
        incoada[nod] = 0; //nodul nu mai e in stiva

        //parcurgem toti vecinii nodului
        for(int i = 0; i < Ca[nod].size(); i++){
            int vecin  = Ca[nod][i].first;
            int cost = Ca[nod][i].second;
            //cout << "nodul " << nod <<" si vecinul " << vecin<<"\n";

            if(D[nod] + cost < D[vecin]){
                D[vecin] = D[nod] + cost;

                if(!incoada[vecin]){
                    C.push(vecin);
                    incoada[vecin] = 1;
                }

                viz[vecin] ++;
                if(viz[vecin] >= mN){
                    ciclun = 1;
                    break;
                }
            }

        }

    }

    if(ciclun)
        fout << "Ciclu negativ!";
    else{
        for(int i = 2; i <= mN; i++)
            fout << D[i] << " ";

    }


}


int main(){
    int N, M;
    fin >> N >> M;
    // fout << 1;
    Graf G(N,M);
    G.Bellman(1);


    return 0;
}