#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#include <algorithm>
using namespace std;

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

const int NM = 5007;
const int INF = 0x3f3f3f3f;

int from, to, cost, N, E, i, x;
bool negative_cycle;

queue <int> Q;
bitset <NM> in_queue(false);
vector < pair<int, int> > G[NM];
vector <int> dist(NM, INF);
vector <int> cnt_in_queue(NM, 0);


int main()
{
    in >> N >> E;
    for (i = 1; i <= E; ++i) {
        in >> from >> to >> cost;
        G[from].push_back({cost, to});
    }

    in.close();

    dist[1] = 0; Q.push(1); in_queue[1] = true;

    while (!Q.empty() && !negative_cycle) {
        x = Q.front(); Q.pop(); in_queue[x] = false;

        for (auto &it: G[x]) {
            if (dist[x] < INF) {
                if (dist[it.second] > dist[x] + it.first) {
                    dist[it.second] = dist[x] + it.first;
                    if (!in_queue[it.second]) {
                        if (cnt_in_queue[it.second] > N)
                            negative_cycle = true;
                        else {
                            Q.push(it.second);
                            in_queue[it.second] = true;
                            cnt_in_queue[it.second] ++;
                        }
                    }
                }
            }
        }
    }

    if (!negative_cycle) {
        for (i = 2; i <= N; ++i)
            out << dist[i] << ' ';
    } else
        out << "Ciclu negativ!";

    out.close();

    return 0;
}