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

using namespace std;

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

const int inf = 0x3f3f3f3f;
int N, M;
bool ciclu_negativ = false;
vector <pair<int, int>> G[50002];
vector <int> Dist, Cnt_Modif, In_Queue;

void bellmanford(int node)
{
    Dist[node] = 0;
    priority_queue <pair<int, int>, vector <pair<int, int>>, greater<pair<int, int>>> Q;
    Q.push({0, node});
    In_Queue[node] = 1;
    while (!Q.empty() && ciclu_negativ == false)
    {
        int current_node = Q.top().second;
        Q.pop();
        In_Queue[current_node] = 0;
        for (const pair <int,int> p : G[current_node])
            if (Dist[p.first] > Dist[current_node] + p.second)
            {
                Dist[p.first] = Dist[current_node] + p.second;
                if (In_Queue[p.first] == 0)
                {
                    if (Cnt_Modif[p.first] > N)
                        ciclu_negativ = true;
                    else
                    {
                        ++Cnt_Modif[p.first];
                        Q.push({Dist[p.first], p.first});
                        In_Queue[p.first] = 1;
                    }
                }
            }
    }
}

int main()
{
    f >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        int x, y, c;
        f >> x >> y >> c;
        G[x].push_back({y, c});
    }
    Dist = vector <int> (N + 1, inf);
    Cnt_Modif = In_Queue = vector <int> (N + 1);
    bellmanford(1);
    if (ciclu_negativ == true)
        g << "Ciclu negativ!";
    else
        for (int i = 2; i <= N; ++i)
            g << Dist[i] << " ";
    f.close();
    g.close();
    return 0;
}