#include <bits/stdc++.h>

namespace BellmanFord{
    using namespace std;
    #ifdef fakeFILES
    std::ifstream fin("input.in");
    std::ofstream fout("input.out");
    #else
    std::ifstream fin("bellmanford.in");
    std::ofstream fout("bellmanford.out");
    #endif
    int const N = 50005, INF = 1e9;
    int n;
    std::vector< pair<int,int> > g[N];

    bool bellman(int start = 1){
        int dist[N],dad[N];
        fill(dist, dist+N, INF);
        fill(dad,dad+N,0);
        dad[start] = start;
        dist[start] = 0;

        set<int> changed_nodes_old,changed_nodes_new;
        changed_nodes_new.insert(start);

        for(int i = 0 ; i <= n + 1 ; i++){

            changed_nodes_old = changed_nodes_new;
            changed_nodes_new.clear();
            /// relax all edges:
            for(int node:changed_nodes_old){
                for(auto edge:g[node]){
                    int v = edge.first; /// neighbour
                    int cost = edge.second;

                    if(dist[node] + cost < dist[v]){
                        changed_nodes_new.insert(v);
                        dist[v] = dist[node] + cost;
                        dad[v] = node;
                    }
                }
            }
        }
        if(changed_nodes_new.size())
            return false;
        for(int node = 1; node <= n ; node ++){
            if(node != start)
                fout << dist[node] << ' ';
        }
        return true;
    }
    void run(){
        int m;
        fin >> n >> m;

        while(m--){
            int x,y,c;
            fin >> x >> y >> c;
            g[x].emplace_back(y,c);
        }

        if(!bellman(1))
            fout << "Ciclu negativ!";
    }
}
/*******************
MOMENTAN LIPSESC:
    - muchii / noduri critice.
    - componente tare conexe.
    - APM kruskal / prim.
    - FLUX de cost max;
    - euler normal la cap.
    - teorema celor 6/5 culori.
    - dist levenstein (usor).
*******************/
int main()
{
    BellmanFord::run();
}