#include <fstream>
#include <vector>
#include <tuple>
#include <limits>
#include <algorithm>
 
using Vertex = int;
using Distance = int64_t;
 
using Edge = std::tuple<Vertex, Vertex, Distance>;
 
bool BellmanFord(std::vector<Distance>& distances, const std::vector<Edge>& graph, int N)
{
    std::vector<int> relax(N, 0);
    for (auto i = 0; i < N; ++i) {
        auto changed = false;
        for (const auto& edge : graph)
        {
            Vertex u, v;
            Distance d;
            std::tie(u, v, d) = edge;
            if ((distances[u - 1] + d) < distances[v - 1])
            {
                ++relax[v - 1];
                changed = true;
                distances[v - 1] = distances[u - 1] + d;
                if (relax[v - 1] == N)
                    return true;
            }
        }
        if (!changed)
            return false;
    }
 
    Vertex u, v;
    Distance d;
    for (const auto& edge : graph) {
        std::tie(u, v, d) = edge;
        if ((distances[u - 1] + d) < distances[v - 1]) {
            return true;
        }
    }
    return false;
}
int main()
{
    std::ifstream fin("bellmanford.in");
    std::ofstream fout("bellmanford.out");
    int N, M;
    fin >> N >> M;
    std::vector<Distance> distances(N, std::numeric_limits<Distance>::max() - 1001);
    std::vector<Edge> edges(M);
    for (int i = 0; i < M; ++i) {
        Vertex u, v;
        Distance d;
        fin >> u >> v >> d;
        edges[i] = std::make_tuple(u, v , d);
    }
    distances[0] = 0;
    const auto negatives = true;//BellmanFord(distances, edges, N);
    if (negatives) {
        fout << "Ciclu negativ!";
        return 0;
    }

    for (auto it = distances.begin() + 1; it != distances.end(); ++it) {
        fout << *it << " ";
    }    
    return 0;
}