#include <iostream>
#include <random>
#include <fstream>
#include <stack>
#include <bitset>
#include <queue>
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
vector<pair<int, int>> L[50005];
int cnt[50005], dist[50005];
bitset<50006> viz;
int n, m;
bool cycle;
void bel()
{
    viz[1] = 1;
    queue<int> q;
    cnt[1] = 1;
    q.push(1);
    while (!q.empty() && !cycle)
    {
        int curr = q.front();
        q.pop();
        viz[curr] = 0;
        for (auto it : L[curr])
            if (dist[it.first] > dist[curr] + it.second)
            {
                if (cnt[it.first] > n)
                    cycle = 1;
                dist[it.first] = dist[curr] + it.second;
                if (!viz[it.first])
                {
                    viz[it.first] = 1;
                    cnt[it.first]++;
                    q.push(it.first);
                }
            }
    }
}
int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        fin >> x >> y >> c;
        L[x].push_back({ y,c });
    }
    for (int i = 2; i <= n; i++)
        dist[i] = 2e9;
    bel();
    if (cycle)
        fout << "Ciclu negativ!\n";
    else for (int i = 2; i <= n; i++)
        fout << dist[i] << " ";
    return 0;
}