#include <bits/stdc++.h>
#define oo 0x3f3f3f3f
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n, m;
int d[50001],cnt[50001];
vector<pair<int, int> > edge[50001];
queue<int> q;
bitset<50001> inq;

void BellmanFord()
{
    int ac;
    bool negcyc = false;
    for (int i = 1; i <= n; i++)
        d[i] = oo;
    d[1] = 0;
    q.push(1);
    inq[1] = 1;
    while (!q.empty() && !negcyc)
    {
        ac = q.front();
        q.pop();
        inq[ac] = false;
        for(auto i : edge[ac])
            if (d[ac] < oo)
            {
                if (d[i.first] > d[ac] + i.second)
                {
                    d[i.first] = d[ac] + i.second;
                    if (!inq[i.first])
                    {
                        if (cnt[i.first] > n)
                            negcyc = true;
                        else {
                            q.push(i.first);
                            inq[i.first] = 1;
                            cnt[i.first]++;
                        }
                    }
                }
            }
    }
    if (!negcyc)
        for (int i = 2; i <= n; i++)
            fout << d[i] << " ";
    else fout << "Ciclu negativ!\n";
}

int main()
{
    int x, y, cost;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        edge[x].push_back({ y,cost });
    }
    BellmanFord();
    fin.close();
    fout.close();
    return 0;
}