#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define cin in
#define cout out

using namespace std;

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

const int NMAX = 1e5 + 5;
int n, m, p, i, dist[NMAX], nodes[NMAX];
vector < pair < int, int > > g[NMAX];

int main()
{
    cin >> n >> m ;
    for(i = 1; i <= m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b,c});
    }
    for(i = 1; i <= n; ++i)
        dist[i] = INF;
    dist[1] = 0;
    queue < int > q;
    q.push(1);
    while(!q.empty()) {
        int nodcur = q.front();
        q.pop();
        for(auto vec : g[nodcur]) {
            int vecur = vec.first;
            int vecost = vec.second;
            if(dist[vecur] > dist[nodcur] + vecost) {
                dist[vecur] = dist[nodcur] + vecost;
                nodes[vecur]++;
                if(nodes[vecur] > n) {
                    cout << "Ciclu negativ!";
                    return 0;
                }
                q.push(vecur);
            }
        }
    }
    for(i = 2; i <= n; ++i)
        cout << dist[i] << ' ';

    return 0;
}