#include<fstream>
# define inf 9999
using namespace std;

int v[250000][3],dist[50001];

int main()
{int i=0,j,n,m,a,b,c,gasit=1;
 ifstream f("bellmanford.in");
 f>>n>>m;
 while(f>>a>>b>>c)
   {v[i][0]=a;
    v[i][1]=b;
    v[i][2]=c;
    i++;
    }  
 f.close();
 for(i=2;i<=n;i++)  dist[i]=inf; 
 dist[1]=0; 
 i=1;
 while(gasit==1 && i<=n)
   {gasit=0;
    for(j=0;j<m;j++)  
     {a=v[j][0];
      b=v[j][1];
      c=v[j][2];
      if(dist[a]+c<dist[b])   
        {dist[b]=dist[a]+c;
         gasit=1;
         }
      }
     i++; 
     }  
 ofstream g("bellmanford.out");     
 if(gasit==1)  g<<"Ciclu negativ!";
    else       
    for(i=2;i<=n;i++)  g<<dist[i]<<" ";   
 g.close();  
 return 0;
}