#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <iterator>
#include <climits>
#include <utility>
#include <memory>

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

const int INF = INT_MAX;

std::vector<int> dijkstra(std::vector<std::vector<std::pair<int, int>>> const &adj) {
    std::vector<int> distances(adj.size(), INF);
    distances[0] = 0;
    std::priority_queue<std::pair<int,int>> pq;
    pq.emplace(0, 0);
    std::vector<bool> processed(adj.size(), false);
    while(!pq.empty()) {
       const int node = pq.top().second;
       pq.pop();
       if(processed[node])
           continue;
       processed[node] = true;
       for(auto p : adj[node]) {
            const int n = p.first, w = p.second;
            distances[n] = std::min(distances[n], distances[node]+w);
            pq.emplace(-distances[n], n);
       }
    }

    for(auto &d : distances)
        if(d==INF)
            d=0;
    return distances;
}



std::unique_ptr<std::vector<int>>
    bellmanFord(std::vector<std::vector<std::pair<int,int>>> const &adj) {
    std::vector<int> distances(adj.size(), INF);
    distances[0] = 0;
    for(int i = 0; i<adj.size(); i++) {
        for(int a = 0; a<adj.size(); a++) {
            for(auto p : adj[a]) {
                const int b = p.first, w = p.second;
                if(distances[a]+w < distances[b]) {
                    distances[b] = distances[a]+w;
                    if(a == adj.size())
                        return nullptr;
                }
            }
        }
    }
    return std::make_unique<std::vector<int>>(distances);
}

int main() {
    int n, m, s;
    fin >> n >> m;
    std::vector<std::vector<std::pair<int, int>>> adj(n);
    while(m--) {
        int a, b, w;
        fin >> a >> b >> w;
        a--, b--;
        adj[a].emplace_back(b, w);
    }

    const auto distances_ptr = bellmanFord(adj);
    if(distances_ptr) {
        const auto &distances = *distances_ptr;
        std::copy(distances.begin()+1, distances.end(),
                  std::ostream_iterator<int>(fout, " "));
    }else {
        fout << "Ciclu negativ!\n";
    }
    return 0;
}