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

using namespace std;

const int NMAX = 5e4+10;

vector <pair <pair<int, int>, int>> edges(NMAX);

long long cost[NMAX];

int main()
{
    ifstream cin ("bellmanford.in");
    ofstream cout ("bellmanford.out");

    int n, m, a, b, lgth;
    cin >> n >> m;
    for (int i=0; i<m; i++)
    {
        cin >> a >> b >> lgth;
        edges.push_back({{a, b}, lgth});
    }
    for (int i=1; i<=n; i++) cost[i] = 1e17;
    cost[1] = 0;
    for (int i=1; i<=n-1; i++)
    {
        for (auto it : edges)
        {
            a = it.first.first; b = it.first.second; lgth = it.second;
            if(cost[a] == 1e17) continue;
            cost[b] = min(cost[b], cost[a]+lgth);
        }
    }
    for (auto it : edges)  /// n-th trial
    {
        a = it.first.first; b = it.first.second; lgth = it.second;
        if (cost[b] > cost[a]+lgth)
        {
            cout << "Ciclu negativ!" << '\n';
            return 0;
        }
    }
    for (int i=2; i<=n; i++)
    {
        cout << cost[i] << " ";
    }
    cout << '\n';
    return 0;
}