#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define MAX_N 50000

const int INF = 1e9;

struct node
{
    int other, cost;
};

int n, m;
vector <int> timesInserted, dist;
bitset <MAX_N + 1> inQueue;
vector <vector <node> > graph;
queue <int> q;

void solve(int src)
{
    dist.resize(n + 1, INF);
    timesInserted.resize(n + 1);
    q.push(src);
    timesInserted[src] = 1;
    inQueue[src] = 1;
    dist[src] = 0;
    bool negativeCycle = 0;
    while(!q.empty()  &&  !negativeCycle)
    {
        int x = q.front();
        q.pop();
        inQueue[x] = 0;
        for(node neighbour : graph[x])
        {
            if(dist[neighbour.other] > dist[x] + neighbour.cost)
            {
                dist[neighbour.other] = dist[x] + neighbour.cost;
                if(!inQueue[neighbour.other])
                {
                    q.push(neighbour.other);
                    inQueue[neighbour.other] = 1;
                    timesInserted[neighbour.other] ++;
                    if(timesInserted[neighbour.other] > n)
                        negativeCycle = 1;
                }
            }
        }


    }
    if(negativeCycle)
        cout << "Ciclu negativ!";
    else
        for(int i = 2; i < dist.size(); i ++)
            cout << dist[i] << " ";
}

int main()
{
    ios_base ::sync_with_stdio(0);
    cin.tie(0);

    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    cin >> n >> m;
    graph.resize(n + 1);

    for(int i = 1; i <= m; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        graph[a].pb({b, c});
    }

    solve(1);
    return 0;
}