#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

const int NMax = 50005;
const int oo = (1 << 30);

vector < pair < int, int > > G[NMax];
queue < int > Q;

int N,M;
bool InCoada[NMax];
int Cate[NMax];
int D[NMax];
int ciclu;
void Read(){
    f >> N >> M;
    for(int  i = 1; i <= M;i++){
        int x,y,c;
        f >> x >> y >> c;
        G[x].push_back(make_pair(y,c));
    }
}

void BellmanFord(int nodStart){
    for(int i = 1; i <= N;i++)
        D[i] = oo;
    D[nodStart] = 0;

    Q.push(nodStart);
    InCoada[nodStart] = true;

    while(!Q.empty() && !ciclu){

        int nodCurent = Q.front();
        Q.pop();
        InCoada[nodCurent] = false;

        Cate[nodCurent]++;
        if(Cate[nodCurent] >= N)
            ciclu = 1;

        for(unsigned int i  = 0; i < G[nodCurent].size();i++){
            int Vecin = G[nodCurent][i].first;
            int Cost = G[nodCurent][i].second;

            if(D[Vecin] > D[nodCurent] + Cost){
                D[Vecin] = D[nodCurent] + Cost;
                if(!InCoada[Vecin])
                    Q.push(Vecin);
                    InCoada[Vecin] = true;
            }
        }

    }

}


int main()
{
    Read();

    BellmanFord(1);
    if(ciclu == 0)
    for(int i = 2; i <= N;i++)
        g << D[i] << " ";
    else g << "Ciclu negativ!";

    return 0;
}