#include <iostream>
#include <vector>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define inf 0x3f3f3f3f
using namespace std;
vector <pair<int,int> > lv[50002];
queue <int> q;
vector <pair<int,int> >:: iterator ii;
int d[50002],n,m,a,b,c,nr[50002];
int main()
{
    int nc;
    FILE *f=fopen("bellmanford.in","r");
    fscanf(f,"%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
          fscanf(f,"%d%d%d",&a,&b,&c);
          lv[a].push_back(make_pair(b,c));
    }
    memset(d,inf,sizeof(d));
     q.push(1);
     d[1]=0;
     while(!q.empty())
     {
         nc=q.front();
         q.pop();
         for(ii=lv[nc].begin();ii!=lv[nc].end();++ii)
         {
             if(d[ii->first]>d[nc]+ii->second)
             {d[ii->first]=d[nc]+ii->second;
              q.push(ii->first);
              ++nr[ii->first];
              if(nr[ii->first]>=n)
                 printf("Ciclu negativ!\n");

             }
         }
     }
      ;
     FILE *f1=fopen("bellmanford.out","w");
      for(int i = 2; i <= n; ++i)
        fprintf(f1,"%d ", d[i]);
    return 0;
}