#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

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

const int maxN = 50005;
const int maxM = 250005;
const ll INF = 0x3f3f3f3f3f3f3f3f;

struct Edge {
    int a, b; ll c;
} edges[maxM];

int N, M, ptr, p[maxN];
ll dp[maxN];

int main(){
    f >> N >> M;
    for(int i = 0, a, b; i < M; i++){
        ll c;
        f >> a >> b >> c;
        edges[i] = {a, b, c};
    }

    ptr = -1;
    fill(dp+2, dp+N+1, INF);
    for(int iter = 0; iter < N && ptr; iter++){
        ptr = 0;
        for(int i = 0; i < M; i++){
            int u = edges[i].a;
            int v = edges[i].b;
            ll w = edges[i].c;

            if(dp[v] > dp[u]+w){
                dp[v] = dp[u]+w;
                p[v] = u;
                ptr = v;
            }
        }
    }

    if(!ptr){
        for (int i = 2; i <= N; i++)
        {
            g << dp[i] << " ";
        }
        return 0;
    }

    g << "Ciclu negativ!";
}