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

#define NMAX 50010
#define INF 1000000000

using std::queue;
using std::vector;

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

struct Arc {
    int node, cost;
    Arc(int node, int cost) {
        this->node = node;
        this->cost = cost;
    }
};

int n, m;
vector<Arc> ad[NMAX];

queue<int> q;
int dp[NMAX];
int nr[NMAX];

int main() {
    int i, node;
    int x, y, z;

    fin >> n >> m;
    for (i = 0; i < m; i++) {
        fin >> x >> y >> z;
        ad[x].push_back(Arc(y, z));
    }

    for (i = 2; i <= n; i++)
        dp[i] = INF;

    q.push(1);
    while (!q.empty()) {
        node = q.front(); q.pop();
        for (i = 0; i < (int) ad[node].size(); i++)
            if (dp[node] + ad[node][i].cost < dp[ad[node][i].node]) {
                dp[ad[node][i].node] = dp[node] + ad[node][i].cost;
                q.push(ad[node][i].node);

                if (++nr[ad[node][i].node] == n) {
                    fout << "Ciclu negativ!\n";
                    fout.close();
                    return 0;
                }
            }
    }

    for (i = 2; i <= n; i++)
        fout << dp[i] << ' ';
    fout << '\n';

    fout.close();
    return 0;
}