#include <bits/stdc++.h>
using namespace std;
#define LMAX 50001
vector<pair<int,int> > G[LMAX];
int n,viz[LMAX],dist[LMAX];
void Init(){
    for(int i=1;i<=n;++i)
        dist[i]=INT_MAX;
}
bool BFord(int k){
    queue<int> Q;
    Q.push(k);
    dist[k]=0;
    while(!Q.empty()){
        int nod=Q.front();
        Q.pop();
        ++viz[nod];
        if(viz[nod]==n)
            return 0;
        for(auto it : G[nod])
            if(dist[nod]+it.second<dist[it.first]){
                dist[it.first]=dist[nod]+it.second;
                Q.push(it.first);
            }
    }
    return 1;
}
int main(){
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    int m;
    scanf("%d %d",&n,&m);
    while(m--){
        int st,dr,cost;
        scanf("%d %d %d",&st,&dr,&cost);
        G[st].push_back({dr,cost});
    }
    Init();
    if(BFord(1)==0)
        printf("Ciclu negativ!");
    else for(int i=2;i<=n;++i)
        printf("%d ",dist[i]);
    return 0;
}