#include <cstdio>
#include <queue>
#include <vector>
#include <bitset>
using namespace std;

const int N = 5e4 + 5;
const int INF = 1<<30;
bitset <N> in_queue(0);
vector < pair<int, int> > v[N];
queue <int> q;
int dp[N], cntQ[N];

int main(){
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    int n, m, i, j, x, y, c;
    bool neg_cycle = false;
    scanf("%d %d", &n, &m);
    for(i = 1;i <= m;i++){
        scanf("%d %d %d", &x, &y, &c);
        v[x].push_back({y, c});
    }
    for(i = 2;i <= n;i++){
        dp[i] = INF;
    }
    in_queue[1] = 1;
    q.push(1);
    cntQ[1] = 1;
    int id;
    while(q.empty() == false && neg_cycle == false){
        id = q.front();
        q.pop();
        in_queue[id] = 0;
        for(auto it : v[id]){
            if(dp[it.first] > dp[id] + it.second){
                dp[it.first] = dp[id] + it.second;
                cntQ[it.first]++;
                if(cntQ[it.first] > n){
                    neg_cycle = true;
                }else if(in_queue[it.first] == 0){
                    q.push(it.first);
                    in_queue[it.first] = 1;
                }
            }
        }
    }
    if(neg_cycle == true){
        printf("Ciclu negativ!");
        return 0;
    }
    for(i = 2;i <= n;i++){
        printf("%d ",dp[i]);
    }
    return 0;
}