#include <bits/stdc++.h>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
// #define f cin
// #define g cout
const int inf = (1 << 30);
vector<vector<pair<int, int>>> v;
int n, m, ax[50001], cnt[50001], bif[50001];
struct node
{
    int ind, cost;
    bool operator<(const node &x) const
    {
        return cost > x.cost;
    }
};
priority_queue<node> pq;
int main()
{
    f >> n >> m;
    v.resize(n + 1);
    for (int i = 2; i <= n; i++)
        ax[i] = inf;
    for (int i = 1, x, y, c; i <= m; i++)
        f >> x >> y >> c, v[x].emplace_back(y, c);
    pq.push({1, 0});
    bif[1] = 1;
    while (!pq.empty())
    {
        auto ac = pq.top();
        pq.pop();
        cnt[ac.ind]++;
        bif[ac.ind] = 0;
        if (cnt[ac.ind] == n)
        {
            g << "Ciclu negativ!";
            return 0;
        }
        for (const auto &i : v[ac.ind])
            if (ax[i.first] > ax[ac.ind] + i.second)
            {
                ax[i.first] = ax[ac.ind] + i.second;
                if (!bif[i.first])
                    bif[i.first] = 1, pq.push({i.first, ax[i.first]});
            }
    }
    for (int i = 2; i <= n; i++)
        g << ax[i] << " ";
    return 0;
}