#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int INF = 1000000000;
const int NMAX = 50001;

vector<pair<int, int>> ma[NMAX];
int mc[NMAX];
int cnt[NMAX];
bool in_coada[NMAX];

int main()
{
    int n, m;
    fin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        ma[x].push_back({y, c});
    }

    for (int i = 1; i <= n; i++)
    {
        mc[i] = INF;
        cnt[i] = 0;
        in_coada[i] = false;
    }

    mc[1] = 0;
    queue<int> q;
    q.push(1);
    in_coada[1] = true;

    while (!q.empty())
    {
        int el = q.front();
        q.pop();
        in_coada[el] = false;

        for (auto& muchie : ma[el])
        {
            int a = muchie.first;
            int b = muchie.second;

            if (mc[el] != INF && mc[el] + b < mc[a])
            {
                mc[a] = mc[el] + b;
                if (!in_coada[a])
                {
                    q.push(a);
                    in_coada[a] = true;
                    cnt[a]++;
                    if (cnt[a] >= n)
                    {
                        fout << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }

    for (int i = 2; i <= n; i++)
    {
        fout << mc[i] << " ";
    }

    fin.close();
    fout.close();
    return 0;
}