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

using namespace std;

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

void gyors(int N,int M,vector<Edge>& edges,int start,ofstream &g) {
    vector<int>tav(N+1,INT_MAX);
    vector<bool> iq(N+1,false);
    queue<int>q;

    tav[start]=0;
    q.push(start);
    iq[start]=true;

    while(!q.empty()) {
        int u=q.front();
        q.pop();
        iq[u]=false;

        for (int i=0;i<M;i++) {
            if (edges[i].u==u) {
                int v=edges[i].v;
                int suly=edges[i].suly;

                if (tav[u]!=INT_MAX&&tav[u]+suly<tav[v]) {
                    tav[v]=tav[u]+suly;

                    if (!iq[v]) {
                        q.push(v);
                        iq[v]=true;
                    }
                }
            }
        }
    }

    for (int i=2;i<=N;i++) {
        if (tav[i]==INT_MAX) {
            g<<"Ciclu negativ!"<<endl;
        }else{
            g<<tav[i]<< " ";
        }
    }
    g<<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;
    gyors(N,M,edges,start,g);

    return 0;
}