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

using namespace std;

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

int n, m, viz[50002], cost[50002], rang;
vector<pair<int, int>> G[50002];
queue<pair<int, int>> q;

int bellmanford(int start)
{
    if (viz[start]) return 0;
    q.push({0, start});

    for (int i = 1; i <= n; i++)
        cost[i] = INT_MAX;

    while (!q.empty())
    {
        int cst = -q.front().first, c = q.front().second;
//        cout << c << " " << cst << endl;
        q.pop();

        viz[c]++;
        if (viz[c] > rang + n) return -1;

        if (cst < cost[c])
        {
            cost[c] = cst;
            for (int i = 0; i < G[c].size(); i++)
                q.push({-cost[c]-G[c][i].second, G[c][i].first});
        }
    }
    return 1;
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        G[x].push_back({y, c});
    }
//    for (int i = 1; i<=n; i++)
//    {
//        cout << i << ": ";
//        for (int j = 0; j < G[i].size(); j++)
//            cout << "(" << G[i][j].first << " " << G[i][j].second << ") ";
//        cout << endl;
//    }
    for (int i = 1; i <= n; i++)
        rang += G[i].size();

    int val = bellmanford(1);
    if (val == -1)
    {
        fout << "Ciclu negativ!";
        return 0;
    }
    for (int i = 2; i <= n; i++)
        fout << cost[i] << " ";
    return 0;
}