#include <bits/stdc++.h>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int N_MAX = 5e4 + 1;
const int oo = 1 << 29;

vector<vector<pair<int, int>>> graph(N_MAX, vector<pair<int, int>>());
int N, M;

vector<int> dist(N_MAX, oo);
vector<bool> inQueue(N_MAX, false);
vector<int> cntInQueue(N_MAX, 0);

struct Compare{
    bool operator () (int node_x, int node_y)
    {
        return dist[node_x] > dist[node_y];
    }
};

priority_queue<int, vector<int>, Compare> pq;

void Dijkstra()
{
    pq.push(1);
    inQueue[1] = true;
    dist[1] = 0;
    cntInQueue[1] = 1;

    while(pq.empty() == false)
    {
        int node = pq.top();
        pq.pop();

        inQueue[node] = false;

        for(auto& next : graph[node])
        {
            if(dist[node] + next.second < dist[next.first])
            {
                dist[next.first] = dist[node] + next.second;

                if(inQueue[next.first] == false)
                {
                    inQueue[next.first] = true;
                    pq.push(next.first);
                    cntInQueue[next.first]++;

                    if(cntInQueue[next.first] == N)
                    {
                        fout << "Ciclu negativ!";
                        return;
                    }
                }
            }
        }
    }

    for(int i = 2; i <= N; ++i)
    {
        fout << dist[i] << ' ';
    }
}

int main()
{
    fin >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        int x, y, c;
        fin >> x >> y >> c;

        graph[x].push_back({y, c});
    }

    Dijkstra();
}