#include <bits/stdc++.h>
#define NMax 50000
#define oo 1<<30
#define x first
#define y second
using namespace std;

typedef pair<int, int> Per;
vector<Per> a[NMax+1];
queue<int> q;
int viz[NMax+1];
int d[NMax+1];

int main(){
    FILE* fin = fopen("bellmanford.in","r");
    FILE* fout = fopen("bellmanford.out","w");

    int i,N,M,x,y,z,negativ=0;

    fscanf(fin,"%d %d",&N,&M);
    for(i = 1; i <= M; ++i)
    {
        fscanf(fin,"%d %d %d",&x,&y,&z);
        a[x].push_back({y,z});
    }

    for(i = 2; i <= N; ++i) d[i] = oo;

    q.push(1);
    while(!q.empty() && !negativ)
    {
        x = q.front();
        q.pop();

        for(i = 0; i < a[x].size(); ++i)
        {
            y = a[x][i].x;
            z = a[x][i].y;
            if(d[y] > d[x] + z){
                ++viz[y];
                q.push(y);
                d[y] = d[x] + z;
                if(viz[y] > N) negativ = 1;
            }
        }
    }

    if(negativ) fprintf(fout,"Ciclu negativ!\n");
    else
        for(i = 2; i <= N; ++i)
        fprintf(fout,"%d ",d[i]);


return 0;
}