#include <bits/stdc++.h>

using namespace std;

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

int n,m;
vector<pair<int,int>>g[50005];
int nrq[50005];
bool inq[50005];
int d[50005];
int inf = 1e9;

int main()
{
    in >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x,y,z;
        in >> x >> y >> z;
        g[x].push_back({y,z});
    }
    for (int i = 1; i <= n; i++)
        d[i] = inf;
    queue<int>q;
    q.push(1);
    d[1] = 0;
    inq[1] = true;
    while (!q.empty())
    {
        int nod = q.front();
        q.pop();
        inq[nod] = false;
        for (auto vecin : g[nod])
        {
            if (d[vecin.first] > d[nod] + vecin.second)
            {
                d[vecin.first] = d[nod] + vecin.second;
                if (!inq[vecin.first])
                {
                    if (nrq[vecin.first] > n)
                    {
                        out << "Ciclu negativ!";
                        return 0;
                    }
                    q.push(vecin.first);
                    inq[vecin.first] = true;
                    nrq[vecin.first]++;
                }
            }
        }
    }
    for (int i = 2; i <= n; i++)
        out << d[i] << ' ';
    return 0;
}