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

using namespace std;

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

const int N_MAX = 5e4 + 5, oo = 2e9;
int N, M, NrQ[N_MAX], D[N_MAX];
vector < pair <int, int> > G[N_MAX];
queue <int> q;
bool InQ[N_MAX], ok = 1;

void BellmanFord(){
    for (int i = 2; i <= N; ++i)
        D[i] = oo;
    q.push(1);
    InQ[1] = 1;
    NrQ[1] = 1;
    while (!q.empty() && ok){
        int x = q.front(); q.pop(); InQ[x] = 0;
        for (auto vecin : G[x]){
            int node = vecin.first; int cost = vecin.second;
            if (D[node] > D[x] + cost){
                D[node] = D[x] + cost;
                if (!InQ[node]){
                    q.push(node);
                    InQ[node] = 1;
                    NrQ[node]++;
                    if (NrQ[node] > N){
                        ok = 0;
                        out << "Ciclu negativ!";
                        return;
                    }

                }
            }
        }
    }
    for (int i = 2; i <= N; ++i)
        out << D[i] * (D[i] != oo) << " ";
}

int main(){
    in >> N >> M;
    for (int i = 1; i <= M; ++i){
        int x, y, z; in >> x >> y >> z;
        G[x].push_back(make_pair(y, z));
    }
    BellmanFord();
    out << '\n';
    return 0;
}