#include <bits/stdc++.h>

using namespace std;

vector <pair <int, int>> v[50001];
queue <pair <int, int>> q;
int d[50001];
int vi[50001];

int main()
{
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    int n, m;
    f >> n >> m;
    for(int i = 1; i <= 50000; i++)
        d[i] =  (1 << 30); ///il facem 2^30 ca sa nu strice if ul din for mai jos
    for(int i = 1; i <= m; i++)
    {
        int a, b, c;
        f >> a >> b >> c;
        v[a].push_back(make_pair(b, c));
    }
    q.push(make_pair(1,0));///punem nodul sursa (1) in coada cu distanta 0
    d[1] = 0;
    while(!q.empty())
    {
        pair <int, int> x = q.front(); ///se ia primul elem(nodul curent) din coada
        q.pop();
        if(vi[x.first] == n)
        {
            g << "Ciclu negativ!";
            return 0;
        }
        for(int i = 0; i < v[x.first].size(); i++)
        {
            if(d[v[x.first][i].first] > d[x.first] + v[x.first][i].second) ///verifica daca distanta pana la nodul vecin e mai mare ca distanta de la nodul curent plus arcul catre nodul vecin
            {
                vi[v[x.first][i].first]++;
                d[v[x.first][i].first] = d[x.first] + v[x.first][i].second;
                q.push(v[x.first][i]);///noul vecin adaugat in coada
            }
        }
    }
    for(int i = 2; i <= n; i++)
    {
        if(d[i] == (1 << 30)) g << "0 ";
        else g << d[i] << " ";
    }
    return 0;
}