#include <iostream>
#include <fstream>
#include <set>
#include <vector>
#include <bitset>
using namespace std;

#define MAX 50100
#define START_NODE 0
#define INF 999999999

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

/* pair<cost, nod> */
vector<pair<int, int> > neighbours[MAX];
vector<int> distances(MAX, INF);
int n;

int BellmanFord(int start) {
    bitset<MAX> inQueue(false);
    set<pair<int, int> > s;

    distances[start] = 0;
    s.insert(make_pair(0, start));
    inQueue[start] = true;

    while (!s.empty()) {

        int node = (*s.begin()).second;
        int cost = (*s.begin()).first;

        s.erase(s.begin());

        inQueue[node] = false;

        for (unsigned int i = 0; i < neighbours[node].size(); i++) {
            pair<int, int> neighbour = neighbours[node].at(i);

            if (cost + neighbour.first < distances[neighbour.second]) {
                //if (inQueue[neighbour.second]) {
                 //   return 0;
                //}
                distances[neighbour.second] = cost + neighbour.first;
                s.insert(make_pair(distances[neighbour.second], neighbour.second));
                inQueue[neighbour.second] = true;
            }
        }
    }

    return 1;
}

int main() {
    int m, n1, n2, c;

    in >> n >> m;

    for (int i = 0; i < m; i++) {
        in >> n1 >> n2 >> c;

        neighbours[n1 - 1].push_back(make_pair(c, n2 - 1));
    }

    in.close();

    if (BellmanFord(START_NODE)) {
        for (int i = 1; i < n; i++) {
            out << distances.at(i) << " ";
        }
    }
    else {
        out << "Ciclu negativ!";
    }

    out.close();

    return 0;
}