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

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

int n, m;
int dist[50001];

struct arc{
    int s, f, c; /// start, final, cost
}arce[250001];

//void afis_arce();
void citeste_arce();

///Bellman Ford magic: verific primele n-1 iteratii, apoi o verific pe ultima
void bellman_ford(int &verif_ciclu){

    verif_ciclu = 0;
    for(int iter = 1; iter <= n; ++iter){
        if(verif_ciclu <= iter - 2)
            break;
        for(int a = 1; a <= m; ++a){
            /// x --- > y cu cost c
            int x = arce[a].s, y = arce[a].f, cost = arce[a].c;
            if(dist[x] + cost < dist[y]){
                dist[y] = dist[x] + cost;
                verif_ciclu = iter;
            }
        }
    }
}
int main()
{
    in>>n>>m;
    citeste_arce();

    ///umplu distantele cu valoarea maxima
    for(int i = 1; i<=n; ++i)
        dist[i] = 1111;
    dist[1] = 0; /// nodul de plecare are distanta 0

    int ciclu = 0;
    bellman_ford(ciclu);

    if(ciclu == n) out<<"Ciclu negativ!";
    else
        for(int i = 2; i<=n; ++i)
            out<< dist[i] << ' ';

    return 0;
}

void citeste_arce(){
    for(int i = 1; i<=m; ++i){
        in>>arce[i].s>>arce[i].f>>arce[i].c;
    }
}

/*void afis_arce(){
    for(int i = 1; i<=m; ++i){
        cout<<arce[i].s << ' ';
        cout<<arce[i].f << ' ';
        cout<<arce[i].c << '\n';
    }
}*/