#include <stdio.h>
#include <vector>
#include <queue>
#define N 50000
#define fr(i,a,b) for(int i=a;i<b;++i)
using namespace std;
vector<pair<int,int> >o[N];
queue<int>Q;
int qt[N];
int v,e,d[N];
bool inq[N];
int main(){
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%i%i",&v,&e);
    int x,y,z;
    fr(i,0,e){
        scanf("%i%i%i",&x,&y,&z);
        o[x-1].push_back(make_pair(y-1,z));
        }
    inq[0]=true;
    Q.push(0);
    qt[0]=1;
    while(!Q.empty()){
        int b=Q.front();Q.pop();
        inq[b]=false;
        int s=o[b].size();
        fr(i,0,s){
            int e=o[b][i].first;
            int dt=o[b][i].second;
            if(!qt[e]||d[e]>d[b]+dt){
                d[e]=d[b]+dt;
                if(!inq[e]){
                    Q.push(e);
                    inq[e]=true;
                    if(++qt[e]==v){
                        printf("Ciclu negativ!");
                        return 0;
                        }
                    }
                }
            }
        }
    fr(i,1,v)printf("%i ",d[i]);
    return 0;
    }