#include <fstream>
#include <vector>
#include <tuple>
#include <limits>
#include <algorithm>
#include <unordered_map>
#include <queue>

using Vertex = int;
using Distance = int64_t;
 
using Edge = std::tuple<Vertex, Distance>;

using AdjacencyList = std::unordered_multimap<Vertex, Edge>;

static constexpr auto basicallyInfinity = std::numeric_limits<Distance>::max() - 1001;
 
bool BellmanFord(std::vector<Distance>& distances, const AdjacencyList& graph, int N)
{
    std::queue<Vertex> Q;
    std::vector<bool> inQ(N + 1, false);
    std::vector<int> timesInQ(N + 1, 0);
    Q.push(1);
    inQ[1] = true;
    distances[1] = 0;
    while(!Q.empty()) {        
        Vertex u = Q.front();
        Q.pop();
        inQ[u] = false;
        auto neighbors = graph.equal_range(u);
        for(auto it = neighbors.first; it != neighbors.second; ++it) {
            Vertex v = std::get<0>(it->second);
            Distance d = std::get<1>(it->second);
            if ((distances[u] < basicallyInfinity) && (distances[v] > (distances[u] + d)))
            {
                distances[v] = distances[u] + d;
                if (!inQ[v]) {
                    if (timesInQ[v] > N) {
                        return true;
                    } else {
                        Q.push(v);
                        timesInQ[v] += 1;
                        inQ[v] = 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 + 1, basicallyInfinity);
    AdjacencyList graph;
    for (int i = 0; i < M; ++i) {
        Vertex u, v;
        Distance d;
        fin >> u >> v >> d;
        graph.emplace(u, Edge{v , d});
    }
    distances.front() = 0;
    const auto negatives = BellmanFord(distances, graph, N);
    if (negatives) {
        fout << "Ciclu negativ!";
        return 0;
    }

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