/*
  Bellman-Ford
*/

#include <fstream>
#define inf 1000000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

struct NOD
{
    int nod,cost;
    NOD *urm;
} * vec[50010],*p;

struct coada
{
    int nod;
    coada *urm;
} * prim,*ultim;


long cost[50010],cycle,i,j,n,m,s[50010],frecv[50010],u,v,w;

void add(NOD *&prim, int val1, int val2)
{
    NOD * p;
	p = new NOD;
    p -> nod = val1;
    p -> cost = val2;
    p -> urm = prim;
	prim=p;
}

void add_queue(coada *&prim, coada *& ultim,int val)
{
    coada * p;
	p = new coada;
    p -> nod = val;
    p->urm=NULL;
    ultim-> urm = p;
	ultim=p;
}

int del_queue(coada *&prim)
{
    coada * p;
    int info=prim->nod;
    p=prim;
    prim=prim->urm;
    delete p;
return info;
}



int main()
{
f>>n>>m;
for(i=1; i<=m; i++)
   {f>>u>>v>>w;
   add(vec[u],v,w); 
   }

cost[1]=0;
  for(i=2; i<=n; i++)
     cost[i]=inf;

prim=new coada;
prim->nod=1;
prim->urm=NULL;
ultim=prim;
s[1]=1;
cycle=0;
while(prim&&!cycle)
{
    u=del_queue(prim);s[u]=0;
     for(p=vec[u];p;p=p->urm)
       {
        v=p->nod;w=p->cost;                     
       if(cost[u]+w<cost[v])
      {
      cost[v]=cost[u]+w;
      if(!s[v]&&v!=1)
        if(frecv[v]>n)
          cycle=1;
        else
          {
          s[v]=1;
          frecv[v]++;
          add_queue(prim,ultim,v);               
          }

      }
    }   
}
       
if(cycle)
    {
        g<<"Ciclu negativ!\n";
        return 0;
    }
    for(i=2; i<=n; i++)
        g<<cost[i]<<" ";
return 0;
}