#include <bits/stdc++.h>

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

struct Muchie{
    int u,v,cost;
};

vector <Muchie> muchie;

const int INF = 1e9;

int n,m;

bool circuitNegativ = false;

int viz[50005];

vector <int> BellmanFord(int start, vector <int> &tata){
    vector <int> d(n+1, INF);

    d[start]=0;

    for (int i=1;i<=n-1;i++){
        for (auto m : muchie){
            if (viz[m.u]==i-1){
                if (d[m.u]!=INF && d[m.u]+m.cost < d[m.v]){
                    d[m.v]=d[m.u]+m.cost;
                    viz[m.v]=i;
                    /// tata[m.v]=m.u;
                }
            }
        }
    }

    for (auto m : muchie)
        if (d[m.u]!=INF && d[m.u]+m.cost < d[m.v])
            circuitNegativ=true;

    return d;
}

int main()
{
    f>>n>>m;
    for (int i=1;i<=m;i++){
        int nod1,nod2,c;
        f>>nod1>>nod2>>c;
        muchie.push_back({nod1,nod2,c});
    }

    vector <int> tata(n+1, 0);
    vector <int> dist = BellmanFord(1, tata);

    if (circuitNegativ==true){
        g<<"Ciclu negativ!"<<'\n';
    }
    else {
        for (int i=2;i<=n;i++)
            g<<dist[i]<<" ";
    }
    return 0;
}