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

#define MAX 100001
#define INF 1000000001

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



class Graf{
    public:
    //liste de adiacenta cu costuri
        vector< vector<pair<int, int> > >A;

        //nr noduri
        int mN, mM;
        //vector pt drumurile minime
        //vector<int> D;
        //multimea nodurilor pt care inca n am calculat durmul  minim
        vector <int> F;



        //constructor

        Graf(int N, int M){
            mN = N;
            mM = M;
            //fac marimea de N
            //D.resize(mN+1);

            //pregatesc lista pt N noduri
           A.resize(mN+1);
        }

        void CitireG(int M);
        void Dijkstra(int s);
        void Bellman(int s);

};


void Graf:: CitireG(int M){

    int x,y,c;
    for(int i = 0; i < M; i++){

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




}


void Graf :: Bellman (int s){
    queue <int> C;
    vector <int> D(mN+1, INF);
    vector <int> viz(mN+1, 0);
    vector <bool> incoada(mN+1, 0);

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

    bool ciclun = 0;

    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 < A[nod].size(); i++){
            int vecin  = A[nod][i].first;
            int cost = A[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;
    Graf G(N,M);
    G.CitireG(M);
    G.Bellman(1);



    return 0;
}