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

using namespace std;

#define maxN 50005
#define inf (1 << 30)
#define PB push_back
#define MKP make_pair

queue <int> Q;
vector < pair <int, int> > list[maxN];
int Viz[maxN], Cont[maxN], cost[maxN];


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

    int N, M;
    f >> N >> M;

    while(M --) {
        int x, y, c;
        f >> x >> y >> c;

        list[x].PB(MKP(y, c));
    }

    for(int i = 2; i <= N; ++ i)
        cost[i] = inf;
    Viz[1] = Cont[1] = 1;
    Q.push(1);

    while(! Q.empty()) {
        int nod = Q.front();
        Q.pop();
        Viz[nod] = false;

        for(int i = 0; i < list[nod].size(); ++ i) {
            int nod2 = list[nod][i].first, cost2 = list[nod][i].second;

            if(cost[nod2] <= cost[nod] + cost2) continue;
            ++ Cont[nod2];

            if(Cont[nod2] > N) {
                g << "Ciclu negativ!";
                return 0;
            }

            cost[nod2] = cost[nod] + cost2;

            if(! Viz[nod2]) {
                Viz[nod2] = true;
                Q.push(nod2);
            }
        }
    }

    for(int i = 2; i <= N; ++ i)
        g << cost[i] << " ";

    return 0;
}