#include <bits/stdc++.h>

using namespace std;

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

int n, m, i, nr1, nr2, nr3, aici;
const int maxx = 2147483647, nmax = 50001;


int32_t main()
{
    fin >> n >> m;
    vector <vector <pair<int, int>>> ladj(m);
    queue <int> q;
    vector <long long> dist(n+1, maxx);
    bitset <nmax> inQ(false);
    vector <int> cntInQ(n+1), tata(n+1);

    for (i = 0; i < m; ++i){
        fin >> nr1 >> nr2 >> nr3;
        ladj[nr1].push_back({nr2, nr3});
    }
    fin.close();
    q.push(1);
    dist[1] = 0;
    inQ[1] = true;
    bool negCic = 0;
    while (!q.empty() && !negCic){
        aici = q.front();
        q.pop();
        inQ[aici] = false;
        for (auto &k:ladj[aici]){
            if (dist[k.first] > dist[aici] + k.second && tata[aici] != k.first){
                dist[k.first] = dist[aici] + k.second;
                tata[k.first] = aici;
                if (inQ[k.first]){
                    if (cntInQ[k.first] > n)
                        negCic = 1;
                }
                else{
                    ++cntInQ[k.first];
                    inQ[k.first] = true;
                    q.push(k.first);
                }
            }
        }
    }
    if (negCic){
        fout << "Ciclu negativ!\n";
        return 0;
    }
    for (i = 2; i <= n; ++i){
        fout << dist[i] << ' ';
    }
    fout << '\n';
    fout.close();
    return 0;
}