#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 5e4, INF = 0x3f3f3f3f;
int N, M;
vector<pair<int, int>> G[MAXN + 1];
int viz[MAXN + 1];
int d[MAXN + 1];
queue<int> Q;
bitset<MAXN + 1> inQ;

int main()
{
    fin >> N >> M;
    int a, b, c;
    while (M--)
    {
        fin >> a >> b >> c;
        G[a].emplace_back(b, c);
    }
    for (int i = 2; i <= N; i++)
        d[i] = INF;
    viz[1] = 1;
    Q.push(1);
    bool broken = false;
    while (!Q.empty())
    {
        int n = Q.front();
        Q.pop();
        inQ[n] = 0;
        if (++viz[n] >= N)
        {
            broken = true;
            break;
        }
        for (const auto &x : G[n])
        {
            if (d[n] + x.second < d[x.first])
            {
                d[x.first] = d[n] + x.second;
                if (!inQ[x.first])
                {
                    inQ[x.first];
                    Q.push(x.first);
                }
            }
        }
    }
    if (broken)
        fout << "Ciclu negativ!";
    else
    {
        for (int i = 2; i <= N; i++)
            fout << d[i] << ' ';
    }
    return 0;
}