#include <bits/stdc++.h>
#define MAX 131072

using namespace std;
const int NMAX = 500010;

FILE *IN;

struct edge{
    int x, cost;
};

vector <edge> edges[NMAX];
queue <int> nodes;

int N, M;
int ans[NMAX], cnt[NMAX];

int pos, sign;
char f[MAX];

inline void Read(int &nr){
    sign = 0;
    nr = 0;
    while(f[pos] < '0' || f[pos] > '9'){
        if(f[pos] == '-') sign = 1;
        pos++;
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    while(f[pos] >= '0' && f[pos] <= '9'){
        nr = 10 * nr + f[pos++] - '0';
        if(pos == MAX)
            fread(f, MAX, 1, IN), pos = 0;
    }
    if(sign) nr =- nr;
}

void read(){
    Read(N); Read(M);
    int a, b, C;
    for(int i = 1; i <= M; i++){
        Read(a); Read(b); Read(C);
        edges[a].push_back({b, C});
    }
}

int main(){

    IN = fopen("bellmanford.in", "r");
    freopen("bellmanford.out", "w", stdout);

    read();

    for(int i = 2; i <= N; i++)
        ans[i] = 2e9;

    int ok = true;
    nodes.push(1);
    while(!nodes.empty()){
        int Node = nodes.front();
        cnt[Node]++;
        if(cnt[Node] > N){
            ok = false;
            break;
        }
        nodes.pop();
        for(int i = 0; i < edges[Node].size(); i++){
            if(ans[Node] + edges[Node][i].cost < ans[edges[Node][i].x]){
                ans[edges[Node][i].x] = ans[Node] + edges[Node][i].cost;
                nodes.push(edges[Node][i].x);
            }
        }
    }

    if(!ok){
        printf("Ciclu negativ!");
        return 0;
    }

    for(int i = 2; i <= N; i++)
        printf("%d ", ans[i]);

    return 0;
}