#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;

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

const int INF = 1e9;
vector<vector<pair<int, int>>> adj;

bool spfa(int s, vector<int>& d)
{
    int n = adj.size();
    d.assign(n, INF);
    vector<int> cnt(n, 0);
    vector<bool> inequeue(n, false);
    queue<int> q;

    d[s] = 0;
    q.push(s);
    inequeue[s] = true;
    while (!q.empty())
    {
        int v = q.front();
        q.pop();
        inequeue[v] = false;

        for (auto edge : adj[v])
        {
            int to = edge.first;
            int len = edge.second;

            if (d[v] + len < d[to])
            {
                d[to] = d[v] + len;
                if(!inequeue[to])
                {
                    q.push(to);
                    inequeue[to] = true;
                    cnt[to]++;
                    if(cnt[to] > n)
                        return false;
                }
            }
        }
    }
    return true;
}

int main()
{
    int n, m;
    fin >> n >> m;
    adj.assign(n + 1, {});

    for (int i = 0; i < m; ++i) {
        int a, b, c;
        fin >> a >> b >> c;
        adj[a].push_back({b, c});
    }

    vector<int> d;
    if (!spfa(1, d))
    {
        fout << "Ciclu negativ!\n";
        return 0;
    }

    for (int i = 2; i <= n; i++)
    {
        if (d[i] == INF)
            fout << 0 << " ";
        else
            fout << d[i] << " ";
    }

    return 0;
}