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

#define pb push_back
#define sz size()
#define MAXN 50010
#define MAXM 250010
#define x first
#define y second
const int oo=(int)1e9;
typedef pair<int,int>pii;
typedef vector<pii>vii;
int n,m,a[MAXM],b[MAXM],c[MAXM],dist[MAXN],num[MAXN];
vii g[MAXN];
bool inQ[MAXN];
struct cf{
    bool operator()(const pii &a,const pii &b)const{
        return a.y>b.y;
    };
};

void open(){
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
}

int main(){
    open();
    scanf("%d%d",&n,&m);
    for (int i=0;i<m;i++){
        scanf("%d%d%d",&a[i],&b[i],&c[i]);
        g[a[i]].pb(pii(b[i],c[i]));
    }
    for (int i=1;i<=n;i++){
        dist[i]=oo;
        num[i]=0;
    }
    dist[1]=0;
    priority_queue<pii,vii,cf>pq;
    pq.push(pii(1,0));
    inQ[1]=1;
    while (!pq.empty()){
        pii top=pq.top();
        pq.pop();
        inQ[top.x]=0;
        for (vii::iterator it=g[top.x].begin();it!=g[top.x].end();it++){
            if (dist[it->x]>dist[top.x]+it->y){
                dist[it->x]=dist[top.x]+it->y;
                if (inQ[it->x]) continue;
                inQ[it->x]=1;
                num[it->x]++;
                if (num[it->x]>=n){
                    printf("Ciclu negativ!\n");
                    return 0;
                }
                pq.push(pii(it->x,dist[it->x]));
            }
        }
    }
    for (int i=2;i<=n;i++){
        if (i>2) printf(" ");
        printf("%d",dist[i]);
    }
    printf("\n");
    //system("pause");
    return 0;
}