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

using namespace std;

const int NMAX = 5e4+10;

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

priority_queue <pair<int, int>> q;

long long cost[NMAX];

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

    int n, m, a, b, lgth, cnt=0;
    cin >> n >> m;
    for (int i=0; i<m; i++)
    {
        cin >> a >> b >> lgth;
        node[a].push_back({b, lgth});
    }
    for (int i=1; i<=n; i++) cost[i] = 1e17;
    cost[1] = 0;
    q.push({0, 1});
    while (!q.empty())
    {
        a = q.top().second;
        q.pop();
        for (auto it : node[a])
        {
            b = it.first; lgth = it.second;
            if(cost[a] == 1e17) continue;
            if (cost[b] > cost[a]+lgth)
            {
                cost[b] = cost[a]+lgth;
                q.push({-cost[b], b});
                cnt++;
                if (cnt == n)
                {
                    cout << "Ciclu negativ!" << '\n';
                    return 0;
                }
            }
        }
    }
    for (int i=2; i<=n; i++)
    {
        cout << cost[i] << " ";
    }
    cout << '\n';
    return 0;
}