#include <bits/stdc++.h>
using namespace std;

int n, m, d[50005], cnt[50005];
const int INF = 2000000000;
queue <int> q;
vector <pair <int, int> > v[50005];
int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    scanf("%d%d", &n, &m);
    int x, y, c;
    for(int i = 1; i <= m ; ++i){
        scanf("%d%d%d", &x, &y, &c);
        v[x].push_back(make_pair(y, c));
    }
    for(int i = 1; i <= n ; ++i)
        d[i] = INF;
    d[1] = 0;
    q.push(1);
    while(!q.empty()){
        int nod = q.front();
        ++cnt[nod];
        if(cnt[nod] > n){printf("Ciclu negativ!"); return 0;}
        q.pop();
        for(auto it : v[nod]){
            if(d[it.first] > d[nod] + it.second){
                d[it.first] = d[nod] + it.second;
                q.push(it.first);
            }
        }
    }
    for(int i = 2; i <= n ; ++i)
        printf("%d ", d[i]);
    return 0;
}