#include<bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
#define MAXN 50005
#define INF 2e9
struct Edge{
    int v, c;
    Edge(int a, int b){
        v=a, c=b;
    }
};
int n, m, D[MAXN], InQ[MAXN];
vector<Edge> G[MAXN];
queue<int> Q;

bool solve() {
    int cnt=0;
    for(int i=0; i<=n; ++i)
        D[i]=INF;
    D[1]=0;
    Q.push(1);
    InQ[1]=1;
    while(!Q.empty()){
        int node=Q.front(); Q.pop();
        InQ[node]=0;

        for(auto e : G[node])
            if(D[e.v] > D[node] + e.c) {
                D[e.v]=D[node]+e.c;
                if(!InQ[e.v]) {
                    Q.push(e.v);
                    if(++cnt==2000000)
                        return false;
                }

            }
    }

    return true;
}

int main() {
    int a, b, x;
    fin>>n>>m;
    while(m--) {
        fin>>a>>b>>x;
        G[a].push_back(Edge(b, x));
    }
    if(solve()) {
        for(int i=2; i<=n; ++i)
            fout<<D[i]<<" ";
    } else {
        fout<<"Ciclu negativ!";
        return 0;
    }
    return 0;
}