#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstdlib>
using namespace std;

const int nmx = 50005, inf = 0x3f3f3f3f;

int n;
vector <pair <int,int> > g[nmx]; /// nod,cost

inline void citire(){
    int m, nod1, nod2, cost;
    scanf("%d %d", &n, &m);
    for(; m; --m){
        scanf("%d %d %d", &nod1, &nod2, &cost);
        g[nod1].push_back(make_pair(nod2,cost));
    }
}

inline void rezolvare(){
    queue <int> q;
    vector <int> dist(nmx, inf), cnt(nmx, 0);
    dist[1] = 0;
    q.push(1);
    while(not q.empty()){
        int nod = q.front();
        q.pop();
        int x = g[nod].size();
        for(int i = 0; i < x; ++i)
            if(dist[g[nod][i].first] > dist[nod] + g[nod][i].second){
                dist[g[nod][i].first] = dist[nod] + g[nod][i].second;
                q.push(g[nod][i].first);
                ++cnt[g[nod][i].first];
                if(cnt[g[nod][i].first] > n){
                    printf("Ciclu negativ!\n");
                    exit(0);
                }
            }
    }
    for(int i = 2; i <= n; ++i)
        printf("%d ", dist[i]);
}

int main(){
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);
    citire();
    rezolvare();
    return 0;
}