#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>

const int NMAX=50001,MMAX=250001,INF=2147483647;

std::vector<std::pair<int,int> > vecini[NMAX];

std::queue<int> coada;

int val[NMAX];
bool fol[NMAX];

struct Muchie
{
 int x,y,cost;
};

Muchie muchii[MMAX];

void Init(int n)
{
 for(int i=1;i<=n;i++)
     val[i]=INF;
}

bool Bellman_Ford(int n,int m)
{
 coada.push(1);
 val[1]=0;
 int pas=0;
 while(!coada.empty() && pas<=n*m)
       {
        pas++;
        int x=coada.front();
        coada.pop();
        fol[x]=false;
        for(std::vector<std::pair<int,int> >::iterator i=vecini[x].begin();i!=vecini[x].end();i++)
            {
             int a,b;
             a=i->first; b=i->second;
             if(val[x]+i->second<val[i->first])
                {
                 val[i->first]=val[x]+i->second;
                 if(!fol[i->first])
                    {
                     coada.push(i->first);
                     fol[i->first]=true;
                    }
                }
            }
       }
 for(int i=1;i<=m;i++)
     {
      if(val[muchii[i].y]>val[muchii[i].x]+muchii[i].cost)
         return true;
     }
 return false;
}

int main()
{
 FILE *in=fopen("bellmanford.in","r");
 int n,m;
 fscanf(in,"%d %d ",&n,&m);
 for(int i=1;i<=m;i++)
     {
      int x,y,cost;
      fscanf(in,"%d %d %d ",&x,&y,&cost);
      vecini[x].push_back(std::make_pair(y,cost));
      muchii[i].x=x,muchii[i].y=y,muchii[i].cost=cost;
     }
 fclose(in);
 Init(n);
 FILE *out=fopen("bellmanford.out","w");
 if(Bellman_Ford(n,m))
    fprintf(out,"Ciclu negativ!");
 else
    {
     for(int i=2;i<=n;i++)
         {
          fprintf(out,"%d ",val[i]);
         }
    }
 fclose(out);
 return 0;
}