#include <bits/stdc++.h>
using namespace std;
const int nmx = 5e4 + 50'004;
vector<array<int,2>> ad[nmx];
#if 1
#define cin fin
#define cout fout
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
#endif
const int64_t INF = 1e17;
int n,m;
bool spfa(vector<int64_t>& d) {
    d.assign(n, INF);
    vector<bool> inqueue(nmx, 0);
    queue<int> q;

    d[1] = 0;
    q.push(1);
    inqueue[1] = 1;
    for(int i=1;i<=2*n+1;i++){
        if(q.empty())
            break;
        int v = q.front();
        q.pop();
        inqueue[v] = 0;

        for (auto edge : ad[v]) {
            int to = edge[0];
            int64_t len = edge[1];

            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                if (!inqueue[to]) {
                    q.push(to);
                    inqueue[to] = 1;
                }
            }
        }
    }
    if(q.size()){
        return 0;
    }
    return 1;
}

int main(){
    cin >> n >> m;
    while(m--){
        int u,v,c;
        cin >> u >> v >> c;
        ad[u].push_back({v,c});
    }
    vector<int64_t> d(nmx,INF);
    if(spfa(d)){
        for(int i=2;i<=n;i++)
            cout << d[i] << " ";
    }else{
        cout << "Ciclu negativ!";
    }
}