#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;

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

const int MAXN = 50005;
const int INF = 0x3f3f3f3f;

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

bool negativeCycle;
bool in_queue[MAXN];
int N, M;
int cost[MAXN], count_in[MAXN];

void read() {
    fin >> N >> M;
    int a, b, c;
    for (int i = 0; i < M; ++i) {
        fin >> a >> b >> c;
        G[a].push_back(make_pair(b, c));
    }
}

void init() {
    memset(cost, 0x3f, sizeof(cost));
    cost[1] = 0;
    Q.push(1);
    count_in[1]++;
}

void solve() {
    do {
        int node = Q.front();
        Q.pop();
        in_queue[node] = false;
        vector<pair<int, int> >::iterator it;
        for (it = G[node].begin(); it != G[node].end(); ++it) {
            if (cost[it->first] > cost[node] + it->second) {
                cost[it->first] = cost[node] + it->second;
                if (!in_queue[it->first]) {
                    Q.push(it->first);
                    in_queue[it->first] = true;
                    count_in[it->first]++;//de cate ori am introdus aceste nod in coada SAU
                                          //de cate ori am imbunatatit costul pentru a ajunge aici
                    if (count_in[it->first] > N) {
                        negativeCycle = true;
                        return;
                    }
                }
            }
        }
    }while (!Q.empty());
}

void write() {
    if (negativeCycle)
        fout << "Ciclu negativ!\n";
    else
        for (int i = 2; i <= N; ++i)
            fout << cost[i] << ' ';
}

int main() {
    read();
    init();
    solve();
    write();
    fin.close();
    fout.close();
    return 0;
}