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

using namespace std;

#define INF (1<<30)

struct Edge
{
    int x;
    int y;
    int w;
};

typedef vector<vector<Edge>> CostGraph;



void BellmanFord(int S, const CostGraph &graph)
{
    vector<int> distances(graph.size());
    vector<int> nodeUsedFrequency(graph.size());

    for (int i = 0; i < distances.size(); ++i)
    {
        distances[i] = INF;
        nodeUsedFrequency[i] = 0;
    }

    distances[S] = 0;
    nodeUsedFrequency[S]++;
    queue<int> relaxedNodes;

    relaxedNodes.push(S);

    while (relaxedNodes.size() && nodeUsedFrequency[relaxedNodes.front()] <= graph.size())
    {
        auto node = relaxedNodes.front();

        for (auto& edge : graph[node])
        {
            if (distances[edge.y] > distances[edge.x] + edge.w)
            {
                distances[edge.y] = distances[edge.x] + edge.w;

                relaxedNodes.push(edge.y);

                nodeUsedFrequency[edge.y]++;
            }
        }

        relaxedNodes.pop();
    }

    if (relaxedNodes.size())
    {
        cout << "Ciclu negativ!";
    }
    else
    {
        for (int i = 2; i < graph.size(); ++i)
        {
            cout << distances[i] << " ";
        }
    }

}

int main()
{

#ifndef _DEBUG
    ifstream in("bellmanford.in");
    ofstream out("bellmanford.out");
    
    cin.set_rdbuf(in.rdbuf());
    cout.set_rdbuf(out.rdbuf());

#endif 
    

    int N, M;

    cin >> N >> M;

    CostGraph graph(N + 1);

    for (int i = 1; i <= M; ++i)
    {
        int x, y, w;

        cin >> x >> y >> w;

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

    BellmanFord(1, graph);

    return 0;
}