#include <fstream>
#include <queue>
#include <vector>
#include <iostream>
#define INF 0x3f3f3f3f
#define NM 50005
using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

vector < pair <int, int > > graf[NM];
int use_in_queue[NM];
queue < int > coada;
vector < int > cost(NM, INF);

int main()
{
    int n, m, x, y, c, negative_cycle = 0, nod;
    f >> n >> m;
    for(int i = 1; i <= m; ++i)
    {
        f >> x >> y >> c;
        graf[x].push_back(make_pair(y, c));
    }
    coada.push(1);
    use_in_queue[1] = 1;
    cost[1] = 0;
    while(!coada.empty() && !negative_cycle)
    {

        nod = coada.front();
        use_in_queue[nod]--;
        coada.pop();
        for(int i = 0; i < graf[nod].size(); ++i)
        {
            if(cost[graf[nod][i].first] > cost[nod] + graf[nod][i].second)
            {
                if(use_in_queue[graf[nod][i].first] > n)
                {
                    negative_cycle = 1;
                }
                else
                {
                    cost[graf[nod][i].first] = cost[nod] + graf[nod][i].second;
                    use_in_queue[graf[nod][i].first]++;
                    coada.push(graf[nod][i].first);
                }
            }
        }
    }

    if(!negative_cycle)
    {
        for(int i = 2; i <= n; ++i)
            g << cost[i] << ' ';
        g << '\n';
    }
    else g << "Ciclu negativ!" << '\n';
    f.close();
    g.close();
    return 0;
}