#include<iostream>
#include<vector>
#include<fstream>
#include<limits>
#include<queue>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

vector<vector<pair<int, int>>> g;
int n, m;

vector<int> cost;
vector<int> vis;
vector<int> inqueue;

int bellman(int src)
{
    queue<int> q;
    q.push(src);
    cost[src] = 0;
    while (!q.empty()) {
        int node = q.front();
        vis[node]++;
        if (vis[node] > n)
            return -1;
        q.pop();
        inqueue[node] = 0;

        for (int i = 0; i < g[node].size(); i++) {
            auto p = g[node][i];
            if (cost[node] + p.second < cost[p.first]) {
                cost[p.first] = cost[node] + p.second;
                if (inqueue[p.first] == 0) {
                    inqueue[p.first] = 1;
                    q.push(p.first);
                }
            }
        }
    }
    return 0;
}

int main()
{
    fin >> n >> m;
    g.resize(n + 1);
    inqueue.resize(n + 1);
    vis.resize(n + 1, 0);
    cost.resize(n + 1, numeric_limits<int>::max());

    for (int i = 0; i < m; i++) {
        int x, y, z;
        fin >> x >> y >> z;
        g[x].push_back(make_pair(y, z));
    }

    int res = bellman(1);
    if (res == -1) {
        fout << "Ciclu negativ!" << endl;
    } else {
        for (int i = 2; i < cost.size(); i++)
            fout << cost[i] << " ";
    }

    fout.close();
    fin.close();


}