//SHORTEST PATH FASTER ALGORITHM = DIJKSTRA CU COADA SIMPLA


#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int MAX = 50001;

int cnt_inQ[MAX];
queue<int> Q;
vector<pair<int, int>> G[MAX];

int D[MAX];  //retine costul minim al drumului pana la fiecare nod, care trece doar prin nodurile vizitate
int N, M;
bool inQ[MAX];

bool SPFA() {
    int i, vf, nod, cost, lg;
    bool not_ok = false;
    while (!Q.empty() && !not_ok) {
        vf = Q.front();
        Q.pop();
        inQ[vf] = false;
        lg = G[vf].size();
        for (i = 0; i < lg; i++) {
            nod = G[vf][i].first;
            cost = G[vf][i].second;
            if (D[vf] + cost < D[nod]) {
                D[nod] = D[vf] + cost;
                if(!inQ[nod])
                    if(cnt_inQ[nod] > N)    //avem circuit negativ
                        not_ok = true;
                    else {
                        Q.push(nod);
                        inQ[nod] = true;
                        ++cnt_inQ[nod];
                    }

            }
        }
    }
    return not_ok;
}

int main() {

    int x, y, cost;
    in >> N >> M;
    for (int i = 1; i <= N; i++)
        D[i] = 1000000;
    D[1] = 0;

    for (int i = 1; i <= M; i++) {
        in >> x >> y >> cost;
        G[x].push_back (pair<int, int> (y, cost));
        if(x == 1) {
            D[y] = cost;
            Q.push(y);
            inQ[y] = true;
        }
    }

    if(SPFA()) {
        out << "Ciclu negativ!";
        return 0;
    }

    for (int i = 2; i <= N; i++)
        if (D[i] < 1000000)
            out << D[i] << ' ';
        else
            out << 0 << ' ';

    return 0;
}