#include <iostream>
#include <vector>
#include <fstream>
#include <limits.h>

using namespace std;

struct Edge {
    int u;
    int v;
    int suly;
};

void BellmanFord(int N,int M, vector<Edge>&edges,int start,ofstream &g) {
    vector<int> tav(N+1,INT_MAX);
    tav[start]=0;

    for (int i=0;i<N-1;i++) {
        for (int j=0;j<M;j++) {
            int u=edges[j].u;
            int v=edges[j].v;
            int suly=edges[j].suly;
            if (tav[u]!=INT_MAX&&tav[u]+suly<tav[v]) {
                tav[v]=tav[u]+suly;
            }
        }
    }

    for (int i=2;i<=N;i++) {
        if (tav[i]==INT_MAX) {
            g<<"Ciclu negativ!"<<endl;
        } else {
            g<<tav[i]<<" ";
        }
    }
    cout << endl;
}

int main() {
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    int N,M;
    f>>N>>M;

    vector<Edge>edges(M);

    for (int i=0;i<M;i++) {
        f>>edges[i].u>>edges[i].v>>edges[i].suly;
    }
    f.close();
    int start = 1;
    BellmanFord(N,M,edges,start,g);

    return 0;
}