#include <iostream>
#include <vector>
#include <fstream>
#include <queue>
#include <vector>
#include <utility>

using namespace std;

class BellmanFord{

    public:
        BellmanFord(int, string, string);
        ~BellmanFord();
        void ReadData();

        void Start();
        void Interpret();

    private:
        int numOfElements, N, M;
        fstream in, out;
        queue<int> coada;
        int *frecventa, *distanta;
        bool *inQueue, ok = true;
        struct muchie{
            int nod, cost;
        };
        vector<muchie> *vecini;

        void Prepare();

};
BellmanFord::BellmanFord(int n, string fin, string fout){

    numOfElements = n;

    in.open(fin.c_str(), ios::in);
    out.open(fout.c_str(), ios::out);

    frecventa = new int [numOfElements];
    vecini = new vector<muchie> [numOfElements];
    distanta = new int [numOfElements];
    inQueue = new bool [numOfElements];
}
void BellmanFord::ReadData(){

    in >> N >> M;
    for (int i = 1; i <= M; i++){

        int a;
        muchie b;
        in >> a >> b.nod >> b.cost;
        vecini[a].push_back(b);
    }
    Prepare();
}
void BellmanFord::Prepare(){

    coada.push(1);
    inQueue[1] = 1;
    fill(distanta + 1, distanta + numOfElements, 1<<30);
    distanta[1] = 0;
    fill(frecventa, frecventa + numOfElements, 0);

}
void BellmanFord::Start(){

    while (ok && !coada.empty()){

        int x = coada.front();
        coada.pop();
        inQueue[x] = 0;
        for (int i = 0; i < vecini[x].size(); i++){

            int y = vecini[x][i].nod;
            int cost = vecini[x][i].cost;

            if (distanta[x] + cost < distanta[y]){
                distanta[y] = distanta[x] + cost;
                if (!inQueue[y]){

                    if (frecventa[y] > N) ok = false;
                        else{
                            coada.push(y);
                            inQueue[y] = 1;
                            frecventa[y]++;
                        }
                }

            }
        }

    }

}
void BellmanFord::Interpret(){

    if (ok == false) out << "Ciclu negativ!" << endl;
        else{
            for (int i = 2; i <= N; i++)
                out << distanta[i] << " ";
        }
}

BellmanFord::~BellmanFord(){

    in.close();
    out.close();

    delete []frecventa;
    delete []vecini;
    delete []distanta;
    delete []inQueue;
}

int main()
{
    BellmanFord A(500001, "bellmanford.in", "bellmanford.out");

    A.ReadData();
    A.Start();
    A.Interpret();

    return 0;
}