#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>

#define inf 19999999
#define N 50010

using namespace std;

struct Nod{
    int catre;
    int cost;
};

int distante [N];
vector <Nod> graf[N];
int viz[N];
int n;
queue <int> q;

void citire(){
    scanf ("%d", &n);
    int m;
    scanf ("%d", &m);
    while (m --){
        Nod x;
        int y;
        scanf ("%d %d %d", &y, &x.catre, &x.cost);
        graf[y].push_back (x);
    }
}

void belmanFord (int nod){
    for (int i = 1; i <= n; ++ i){
        distante[i] = inf;
    }
    distante[nod] = 0;
    q.push(nod);
    while (!q.empty()){
        nod = q.front();
        q.pop();
        viz[nod] ++;
        if (viz[nod] == n){
            printf ("Ciclu negativ!\n");
            exit(0);
        }

        for (unsigned int i = 0; i < graf[nod].size(); ++ i){
            if (distante[graf[nod][i].catre] > distante[nod] + graf[nod][i].cost){
                distante[graf[nod][i].catre] = distante[nod] + graf[nod][i].cost;
                q.push(graf[nod][i].catre);
            }
        }
    }
}

void afis(){
    for (int i = 2; i <= n; ++ i){
        printf ("%d ", distante[i]);
    }
    printf ("\n");
}

int main()
{
    freopen ("bellmanford.in", "r", stdin);
    freopen ("bellmanford.out", "w", stdout);

    citire();
    belmanFord(1);
    afis();

    return 0;
}