#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define pb push_back

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int oo = 0x3f3f3f3f;

int n;
vector<int> cst, cnt;
vector<vector<pii>> e;

void read(), bellmanford();

int main()
{
    read();
    bellmanford();

    for (int i = 2; i <= n; i++)   
        fout << cst[i] << ' ';
   
    return 0;
}

void read() {
    int m; fin >> n >> m;
    e.resize(n+2); cst.resize(n+2, oo); cnt.resize(n+2);
    while (m--){
        int a, b, c; fin >> a >> b >> c;
        e[a].pb({b,c});
    }
}
void bellmanford(){
    cst[1] = 0;
    queue<pii> s; s.push({0, 1});
    while (!s.empty()){
        int c, from; 
        tie(c, from) = s.front();
        s.pop();
        for (auto it: e[from]){
            int to, cm; tie(to, cm) = it;
            if (c + cm < cst[to]){
                cnt[to]++;
                if (cnt[to] >= n+2){
                    fout << "Ciclu negativ!";
                    exit(0);
                }

                cst[to] = c + cm;
                s.push({cst[to], to});
            }
        }
    }
}

//14:25