#include <fstream>
#include <vector>
#include <iterator>

using namespace std;

struct ut{
    unsigned short hova;
    short hossz;
};

struct csucs{
    vector<ut> szomszedok;
    int tav0 = (1<<29);
}*csucsok;

int main()
{
    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");

    unsigned short N;
    int M;
    in>>N>>M;
    csucsok = new csucs [N];
    for(;M;--M){
        unsigned short honnan, hova;
        short hossz;
        in>>honnan>>hova>>hossz;
        ut temp;
        temp.hossz=hossz;
        temp.hova=hova-1;
        csucsok[honnan-1].szomszedok.push_back(temp);
    }
    csucsok[0].tav0=0;

    for(unsigned short j=0;j<N-1;++j)
        for(unsigned short i=0;i<N;++i){
            vector<ut>::iterator it;
            for(it = csucsok[i].szomszedok.begin(); it!= csucsok[i].szomszedok.end(); it++){
                if(csucsok[(*it).hova].tav0 > csucsok[i].tav0 + (*it).hossz)
                    csucsok[(*it).hova].tav0 = csucsok[i].tav0 + (*it).hossz;
            }
            if(csucsok[0].tav0<0){
                out<<"Ciclu negativ!";
                return 0;
            }
        }

    for(int i=1;i<N;++i)
        out<<csucsok[i].tav0<<" ";
}