#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 5e4 + 5, INF = 1e9;
int N, M;

int dist[N_MAX];
int updateCount[N_MAX];
bitset<N_MAX> inQueue;

struct Edge
{
    int v, d;

    Edge(int _v, int _d) :
        v(_v), d(_d) { }
};

vector<Edge> G[N_MAX];

void SetInput(string name)
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    (void)!freopen((name + ".in").c_str(), "r", stdin);
    (void)!freopen((name + ".out").c_str(), "w", stdout);
}

void ReadInput()
{
    cin >> N >> M;

    for(int i = 0, v1, v2, d; i < M; i++)
    {
        cin >> v1 >> v2 >> d;
        G[v1].emplace_back(v2, d);
    }
}

bool BellmanFord(int start) /// returneaza false daca exista un ciclu negativ
{
    for(int i = 1; i <= N; i++)
        dist[i] = INF;

    queue<int> Q;

    dist[start] = 0;
    Q.push(start);
    inQueue[start] = 1;

    while(not Q.empty())
    {
        int v = Q.front();
        int d = dist[v];

        Q.pop();
        inQueue[v] = 0;

        for(auto& [fiu, cost] : G[v])
            if(dist[fiu] > d + cost)
            {
                dist[fiu] = d + cost;
                if(not inQueue[fiu])
                {
                    Q.push(fiu);
                    inQueue[fiu] = 1;
                    updateCount[fiu]++;

                    if(updateCount[fiu] >= N) /// Exista ciclu negativ!
                        return false;
                }
            }
    }

    return true;
}

void Solve()
{
    bool canAnswer = BellmanFord(1);

    if(canAnswer)
    {
        for(int i = 2; i <= N; i++)
            cout << dist[i] << ' ';
        cout << '\n';
    }
    else
        cout << "Ciclu negativ!\n";
}

int main()
{
    SetInput("bellmanford");

    ReadInput();
    Solve();

    return 0;
}