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

#define nMax 50010
#define oo 1 << 30
#define min(a,b) ((a<b)?a:b)

using namespace std;

class nod{
public:
    int catre;
    int cost;
    nod(int Catre, int Cost){
        catre = Catre;
        cost = Cost;
    };
};
int n;
vector <nod> graf[nMax];
int d[nMax];
int viz[nMax];

queue <int> q;

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

void dijkstra(int nod){
    for(int i = 1; i <= n; ++ i){
        d[i] = oo;
    }
    d[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(d[graf[nod][i].catre] > d[nod] + graf[nod][i].cost){
                d[graf[nod][i].catre] = d[nod] + graf[nod][i].cost;
                q.push(graf[nod][i].catre);
            }
        }
    }
}

void afisare(){
    for(int i = 2; i <= n; ++ i){
        if(d[i] == oo){
            d[i] = 0;
        }
        printf("%d ", d[i]);
    }
}

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

    citire();
    dijkstra(1);
    afisare();

    return 0;
}