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

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


#define INF 0x3f3f3f3f

class Graph{
private:
    std::vector<std::vector<std::pair<int, int>>> adj;
    std::vector<int>frec;
    std::vector<int>cost_minim;
    int V;
public:
    Graph(int v) {
        V = v+1;
        frec.resize(V);
        cost_minim.resize(V, INF);
        adj.resize(V);
    }

    void addEdge(int s, int d, int c) {
        adj[s].push_back({d, c});
    }

    void bellmanFord(int s) {
        cost_minim[s] = 0;
        std::queue<int>q;
        q.push(s);

        while(!q.empty()) {
            int c = q.front();
            frec[c]++;
            q.pop();
            if(frec[c] >=V) {fout << "Ciclu negativ!"; return; }
            
            for(const std::pair<int, int>& v : adj[c]) {
                int dest = v.first;
                int cost = v.second;

                if(cost_minim[dest] > cost_minim[c] + cost) {
                    cost_minim[dest] = cost_minim[c] + cost;
                    q.push(dest);
                }
            }
        }

        for(int i=2;i<V;++i) {
            if(cost_minim[i] != INF) fout << cost_minim[i] << " ";
        }
    }
};


int main(void) {
    int n, m, x, y, z;

    fin >> n >> m;
    Graph g(n);

    for(int i=1;i<=m;++i) {
        fin >> x >> y >> z;
        g.addEdge(x, y, z);
    }

    g.bellmanFord(1);
}