#include<cstdio>
#include<vector>
#include<queue>
#define inf 2000000000
using namespace std;
vector<pair<int,int> > g[50010];
queue<int> q;
int dist[50010],vc[50010],nr[50010];
vector<pair<int,int> >::iterator it;
int main (){
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    int n,m,i,x,y,c,nod;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&c);
        g[x].push_back(make_pair(y,c));
    }
    q.push(1);
    for(i=2;i<=n;i++)
        dist[i]=inf;
    while(!q.empty()){
        nod=q.front();
        q.pop();
        vc[nod]=0;
        if(dist[nod]<inf)
            for(it=g[nod].begin();it!=g[nod].end();it++)
                if(dist[it->first]>dist[nod]+it->second){
                    dist[it->first]=dist[nod]+it->second;
                    if(vc[it->first]==0){
                        if(nr[it->first]>n){
                            printf("Ciclu negativ!");
                            return 0;
                        }
                        q.push(it->first);
                        vc[it->first]=1;
                        nr[it->first]++;
                    }
                }
    }
    for(i=2;i<=n;i++)
        printf("%d ",dist[i]);
    return 0;
}