#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int N, M;
vector<vector<pair<int, int>>> lisAdiacenta;

vector<int> BellmanFord(const int start)
{
    vector<int> distBMF(N + 1, INF);
    vector<int> viz(N + 1, 0);
    vector<bool> apartCoada(N + 1, false);
    queue<int> coada;

    coada.push(start), apartCoada[start] = 1;
    distBMF[start] = 0;

    while (!coada.empty()) {
        int x = coada.front();
        coada.pop();
        apartCoada[x] = 0;

        for (int i = 1; i < lisAdiacenta[x].size(); i++)
                if (distBMF[x] + lisAdiacenta[x][i].second < distBMF[lisAdiacenta[x][i].first]) {
                    distBMF[lisAdiacenta[x][i].first] = distBMF[x] + lisAdiacenta[x][i].second;      //relaxam
                    viz[lisAdiacenta[x][i].first]++;

                    if(!apartCoada[lisAdiacenta[x][i].first]) {
                        coada.push(lisAdiacenta[x][i].first);
                        apartCoada[lisAdiacenta[x][i].first] = 1;
                    }
                    if(viz[lisAdiacenta[x][i].first] >= N) {
                        distBMF.clear();
                        break;
                    }
                }
    }
    return distBMF;
}


int main()
{
    fin>>N>>M;
    int x, y, c;
    vector<pair<int, int>>aux(1,make_pair(-1,-1));
    for(int i = 0; i <= N+1; ++i) {
        lisAdiacenta.push_back(aux);
    }
    for(int i = 1; i <= M; ++i) {
        fin >> x >> y >> c;
        lisAdiacenta[x].push_back(make_pair(y, c));
    }

    vector<int> distBMF = BellmanFord(1);

    if(distBMF.size()) {
        for(int i = 2; i <= N; i++) {
             fout << distBMF[i] << " ";
             }
}
   else
        fout << "Ciclu negativ!";
    return 0;
}