#include <stdio.h>
#include <vector>
#include <queue>
#define INF (1<<30)

int n,m;
struct lst{int vf,cost;};
std::vector<lst> adiacenta[50001];

std::queue<int> coada;
bool inqueue[50001];
int distanta[50001];
int nrparcurs[50001];
int bf(){
   while (!coada.empty()){
      int X=coada.front();coada.pop();
      inqueue[X]=false;
      for (int i=0;i<adiacenta[X].size();i++){
         int y=adiacenta[X][i].vf;
         int c=adiacenta[X][i].cost;
         if (distanta[X]+c<distanta[y]){
            distanta[y]=distanta[X]+c;
            if (!inqueue[y]){
               inqueue[y]=true;
               coada.push(y);
               ++nrparcurs[y];
               if (nrparcurs[y]==n){
                  return 0;
               }
            }

         }
      }
   }
   return 1;

}


int main(){

   freopen("bellmanford.in","r",stdin);
   freopen("bellmanford.out","w",stdout);


   scanf("%d %d",&n,&m);

   for (int i=1;i<=m;i++){
      int a,b,c;lst tmp;
      scanf("%d %d %d",&a,&b,&c);

      tmp.vf=b;tmp.cost=c;
      adiacenta[a].push_back(tmp);
   }

   for (int i=2;i<=n;i++)distanta[i]=INF;
   distanta[1]=0;
   inqueue[1]=true;
   coada.push(1);

   if (!bf()){
      printf("Ciclu negativ!\n");
      return 0;
   }
   for (int i=2;i<=n;i++)
      printf("%d ",distanta[i]);
   printf("\n");
   return 0;
}