#include <fstream>

using namespace std;

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

const int mxN = 5e4 + 1, mxM = 25e4 + 1, INF = 1000;

struct muchie{
    int a, b, cost;
};

int n, m, cost[mxN];
muchie muc[mxM];

int main(){
    fin >> n >> m;
    bool cicluNeg = false;
    for(int i = 1; i <= m; i++){
        fin >> muc[i].a >> muc[i].b >> muc[i].cost;
    }
    for(int i = 1; i <= n; i++)
        cost[i] = n * INF + 1;
    cost[1] = 0;

    for(int v = 1; v < n; v++){
        for(int i = 1; i <= m; i++){
            if(cost[muc[i].b] > cost[muc[i].a] + muc[i].cost)
                cost[muc[i].b] = cost[muc[i].a] + muc[i].cost;
        }
    }

    for(int i = 1; i <= m; i++){
        if(cost[muc[i].b] > cost[muc[i].a] + muc[i].cost){
            cost[muc[i].b] = cost[muc[i].a] + muc[i].cost;
            cicluNeg = true;
        }
    }

    if(cicluNeg)
        fout << "Ciclu negativ!";
    else
        for(int i = 2; i <= n; i++)
            fout << cost[i] << " ";
}