#include <bits/stdc++.h>

using namespace std;

struct Muchie {
    int v, c;

    bool operator<(const Muchie& m) const {
        return c < m.c;
    }
};

vector<Muchie> g[50010];
int inQueue[50010];
int viz[50010];
int dist[50010];
int n, m;

int main() {
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
    }
    memset(dist, 0x3f, sizeof(dist));
    priority_queue<Muchie> q;
    q.push({1, 0});
    inQueue[1] = 1;
    dist[1] = 0;
    while(!q.empty())
    {
        int nod = q.top().v;
        int cost = q.top().c;
        q.pop();
        inQueue[nod] = 0;

        for(const auto& vec : g[nod])
        {
            if(cost + vec.c < dist[vec.v])
            {
                dist[vec.v] = cost + vec.c;
                if(inQueue[vec.v] == 0)
                {
                    q.push({vec.v, dist[vec.v]});
                    inQueue[vec.v] = 1;
                    viz[vec.v]++;
                    if(viz[vec.v] >= n)
                    {
                        cout << "Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
    }
    for(int i = 2; i <= n; i++)
        cout << dist[i] << " ";
    return 0;
}