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

using namespace std;

const int NMAX = 50001;
const int INF = (1 << 30);
const int S = 1;

int cost[NMAX], visited[NMAX];
int n, m;
bitset<NMAX> in_queue;
queue<int> nodes_queue;
vector< pair<int, int> > graph[NMAX];

void input(), output();
bool bellmanFord();

int main() {

    input();

    output();

    return 0;
}

bool bellman_ford() {

    for (int i = 2; i <= n; ++i) {
        cost[i] = INF;
    }

    nodes_queue.push(S); in_queue[S] = 1; visited[S] = 1;
    while (!nodes_queue.empty()) {
        int node = nodes_queue.front(); nodes_queue.pop();
        for (vector< pair<int, int> >::iterator it = graph[node].begin(); it != graph[node].end(); ++it) {
            int dst = it->first, cst = it->second;
            if (cost[node] + cst < cost[dst]) {
                ++visited[dst];
                if (visited[dst] > n) {
                    return false;
                }
                cost[dst] = cost[node] + cst;

                if (!in_queue[dst]) {
                    in_queue[dst] = 1;

                    nodes_queue.push(dst);
                }


            }
        }
        in_queue[node] = 0;
    }

    return true;
}

void input() {

    ifstream f("bellmanford.in");

    f >> n >> m;

    for (int i = 0; i < m; ++i) {
        int src, dst, cost;
        f >> src >> dst >> cost;
        graph[src].push_back(make_pair(dst, cost));
    }
}

void output() {

    ofstream g("bellmanford.out");
    if (!bellman_ford()) {
        g << "Ciclu negativ!\n";
    }
    else {
        for (int i = 2; i <= n; ++i) {
            g << cost[i] << " ";
        }
        g << "\n";
    }
}