#include <bits/stdc++.h>
#define pii pair<int, int>
#define node first
#define cost second
#define inf 2147483647
using namespace std;
int n, m, i, j, k;
int dist[50001], cnt[50001];
bool inq[50001];
bool is;
queue<int> q;
vector<pii> graph[50001];

void read();
void solve();
void write();
int main()
{
    read();
    solve();
    write();
    return 0;
}
void read(){
    freopen("bellmanford.in", "r", stdin);
    scanf("%d%d", &n, &m);
    for(i=1; i<=m; ++i){
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        graph[x].push_back({y, c});
    }
    for(i=2; i<=n; ++i) dist[i]=inf;
    return;
}
void solve(){
    q.push(1); inq[1]=true;
    while(!q.empty()){
        int init=q.front(); inq[init]=false; q.pop();
        ++cnt[init];
        if(cnt[init]==n) {is=true; return;}
        for(auto i:graph[init]){
            if(dist[init]+i.cost<dist[i.node]){
                dist[i.node]=dist[init]+i.cost;
                if(!inq[i.node]){
                    inq[i.node]=true;
                    q.push(i.node);
                }
            }
        }
    }
    return;
}
void write(){
    freopen("bellmanford.out", "w", stdout);
    if(is) printf("Ciclu negativ!");
    else for(i=2; i<=n; ++i) printf("%d ", dist[i]);
    return;
}