#include <bits/stdc++.h>
#define NUM 50005
using namespace std;
vector <pair<int, int>> graf[NUM];
bitset <NUM> inCoada;
queue <int> coada;
int dist[NUM];
int frecv[NUM];
int n, m, nod;
int main()
{
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");

    f >> n >> m;
    for(int i = 0; i < m; ++i)
    {
        int a, b, c;
        f >> a >> b >> c;
        graf[a].push_back({b, c});
    }

    for(int i = 0; i <= n; ++i)
    {
        dist[i] = INT_MAX;
    }

    inCoada[1] = 1;
    coada.push(1);
    dist[1] = 0;

    while(!coada.empty())
    {
        nod = coada.front();
        frecv[nod]++;
        if(frecv[nod] == n)
        {
            g << "Ciclu negativ!";
            return 0;
        }
        for(auto vecin : graf[nod])
            if(dist[nod] + vecin.second < dist[vecin.first])
            {
                dist[vecin.first] = dist[nod] + vecin.second;
                if(!inCoada[vecin.first])
                {
                    inCoada[vecin.first] = 1;
                    coada.push(vecin.first);
                }
            }

        inCoada[nod] = 0;
        coada.pop();
    }

    for(int i = 2; i <= n; ++i)
        g << dist[i] << ' ';
    f.close();
    g.close();
}