#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>

# define INF 0x3f3f3f3f

using namespace std;

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

class Graph
{
private:
    //number of nodes
    int n;
    //number of edges
    int e;
    bool oriented;
    //adj list for graph representation
    vector<vector<int>> adj_list;
public:
    Graph(int n, bool oriented)
    {
        this->n = n;
        this->e = 0;
        this->oriented = oriented;
        vector<int> empty;
        for (int i = 0; i < n; i++)
        {
            this->adj_list.push_back(empty);
        }
    }
    virtual ~Graph() {}


    vector<int> bellmanford()
    {
        vector<pair<int, int>> empty;
        vector<vector<pair<int, int>>> adj_list_with_costs(this->n + 1, empty);
        fin >> this->e;
        for (int i = 0; i < this->e; i++)
        {
            int node1, node2, cost;
            fin >> node1 >> node2 >> cost;
            adj_list_with_costs[node1 - 1].push_back(make_pair(node2 - 1, cost));
        }

        queue<int> que;
        vector<bool> in_queue(this->n + 1, false);
        vector<int> distances(this->n + 1, INF);
        vector<int> times_in_queue(this->n + 1, 0);
        vector<int> negative_cycle;

        distances[0] = 0;
        que.push(0);
        in_queue[0] = true;

        while (!que.empty())
        {
            int node = que.front();
            que.pop();
            in_queue[node] = false;

            for (int i = 0; i < adj_list_with_costs[node].size(); i++)
            {
                pair<int, int> neighbour_with_cost = adj_list_with_costs[node][i];
                int neighbour = neighbour_with_cost.first;
                int cost = neighbour_with_cost.second;

                if (distances[neighbour] > distances[node] + cost)
                {
                    distances[neighbour] = distances[node] + cost;
                    times_in_queue[neighbour]++;

                    if (times_in_queue[neighbour] >= this->n)
                    {
                        return negative_cycle;
                    }

                    if (!in_queue[neighbour])
                    {
                        que.push(neighbour);
                        in_queue[neighbour] = true;
                    }
                }



            }
        }

        return distances;
    }


};



int main()
{

    int N;
    fin >> N;
    Graph graph(N, true);
    vector<int> result_bellmanford = graph.bellmanford();
    if (result_bellmanford.size() == 0)
    {
        fout << "Ciclu negativ!";
    }
    else
    {
        for (int i = 1; i < N; i++)
        {
            fout << result_bellmanford[i] << " ";
        }
    }

    return 0;
}