#include<stdio.h>
#include <queue>
#include<vector>
using namespace std;
int n,m,pp=0,dist[50000],front[50000],update[50000];
 queue <int> q;
struct noduri{int b;
           int c;}nod;
vector<noduri>A[50000];

void bellmanford(){
   int i;

   q.push(1);
   update[1]=1;
   front[1]=1;

while(!q.empty() && !pp){
    int x=q.front();
    q.pop();

    for(i=0;i<A[x].size();i++)
        {
            noduri temp=A[x][i];
            if( dist[x] + temp.c < dist[temp.b] ){

                dist[temp.b] = dist[x] + temp.c;
                update[temp.b]++;
                if(update[temp.b] == n-1 )
                    pp = 1;

                if( front[temp.b] == 0){

                    q.push(temp.b);

                    front[temp.b]++;

                }
            }

    }
    front[x]=0;
}
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
scanf("%d%d",&n,&m);
int i,j,a;


for(i=1;i<=m;i++){
  scanf("%d%d%d",&a,&nod.b,&nod.c);
  A[a].push_back(nod);
}



for(i=1;i<=n;i++){
    if(i==1)
       dist[i]=0;
    else
       dist[i]=2000000001;
}
bellmanford();
if(pp){
        printf("Ciclu negativ!");
        return 0;
    }
for(i=2;i<=n;i++)
   printf("%d ",dist[i]);
return 0;
}