#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debug_with_space(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <double, pii> muchie;

const ll NMAX = 100001;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 101;

int dist[NMAX];
vector <pii> v[NMAX];
bool inq[NMAX];
int cnt[NMAX];

int main() {
    ifstream cin("bellmanford.in");
    ofstream cout("bellmanford.out");
    int n, m, i, x, y, z;
    cin >> n >> m;
    for(i = 1; i <= n; i++)
        dist[i] = 2e9;
    for(i = 1; i <= m; i++){
        cin >> x >> y >> z;
        v[x].push_back({y, z});
    }
    queue <int> q;
    q.push(1);
    inq[1] = 1;
    dist[1] = 0;
    while(!q.empty()){
        int node = q.front();
        q.pop();
        inq[node] = 0;
        for(auto x : v[node]){
            if(dist[x.first] > dist[node] + x.second){
                dist[x.first] = dist[node] + x.second;
                cnt[x.first]++;
                if(cnt[x.first] > n - 1){
                    cout << "Ciclu negativ!";
                    return 0;
                }
                if(!inq[x.first]){
                    inq[x.first] = 1;
                    q.push(x.first);
                }
            }
        }
    }
    for(i = 2; i <= n; i++){
        cout << dist[i] << " ";
    }
    return 0;
}