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

using namespace std;

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

const int dim = 50001;
const int infinity = 1000000;
int check[dim], nodes, edges;
vector< pair<int, int> >graph[dim];
queue<int>q;
int d[dim];

void input() {
    in >> nodes >> edges;
    for (int i = 0; i < edges; i++) {
        int u, v, s;
        in >> u >> v >> s;
        graph[u].push_back(make_pair(v, s));
    }
}

int bf(int node) {
    //init
    for (int i = 1; i <= node; i++) {
        d[i] = infinity;
    }
    check[node]++;
    q.push(node);
    d[node] = 0;
    while (q.empty() == false) {
        int u = q.front();
        q.pop();
        for (size_t j = 0; j < graph[u].size(); j++) {
            int vecin = graph[u][j].first;
            int cost = graph[u][j].second;
            if (d[vecin] > d[u] + cost) {
                if (check[vecin] == nodes - 1) {
                    out << "Ciclu negativ!\n";
                    return -1;
                }
                d[vecin] = d[u] + cost;
                q.push(vecin);
                check[vecin]++;
            }
        }
    }
}


int main() {

    input();
    if (bf(1) != -1) {
        for (int i = 2; i <= nodes; ++i) {
            out << d[i] << ' ';
        }
    }

	return 0;
}