// bellman-ford cu dijkstra / priority queue
#include <fstream>
#include <vector>
#include <climits>
#include <queue>

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

int const INF = INT_MAX;
int const nmax = 50005;
int const mmax = 250005;

struct drum {
    int nod;
    int cost;
};
std::vector <drum> adjacency[nmax];

int lungime[nmax];
int nr_relax[nmax];
bool ciclu;
struct ELEMENT {
    int nod;
    int lungime;

    bool operator < (ELEMENT const other) const {
        return lungime < other.lungime;
    }
};
std::priority_queue <ELEMENT> pq;

int main() {
    int n, m;
    fin >> n >> m;
    for (int i = m; i; i--) {
        int nod1, nod2, cost;
        fin >> nod1 >> nod2 >> cost;
        adjacency[nod1].push_back({nod2, cost});
    }
    for (int i = 2; i <= n; i++)
        lungime[i] = INF;
    pq.push({1, 0});
    while (!pq.empty()) {
        ELEMENT top = pq.top();
        pq.pop();
        nr_relax[top.nod]++;
        if (nr_relax[top.nod] > n) {
            ciclu = true;
            break;
        }
        int cnt = adjacency[top.nod].size();
        for (int i = 0; i < cnt; i++) {
            if (lungime[adjacency[top.nod][i].nod] > lungime[top.nod] + adjacency[top.nod][i].cost) {
                lungime[adjacency[top.nod][i].nod] = lungime[top.nod] + adjacency[top.nod][i].cost;
                pq.push({adjacency[top.nod][i].nod, lungime[adjacency[top.nod][i].nod]});
            }
        }
    }
    if (ciclu == true)
        fout << "Ciclu negativ!";
    else {
        for (int i = 2; i <= n; i++)
            fout << lungime[i] << " ";
    }
    return 0;
}