using namespace std;
#include<fstream>
#define INFINIT 2147483647
struct nod
{
       int vf;
       int cost;
       nod*  next;
};
int n,m,d[50005];
nod*  G[50005];
void addarc(short,short,short);
int main()
{
    nod *p;
    int i,x,y,z,ciclu;
    ifstream fin("bellmanford.in");
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
                     fin>>x>>y>>z;
                     addarc(x,y,z);
    }
    fin.close();
    for(i=1;i<=n;++i)
       d[i]=INFINIT;
    d[1]=0;
    for(i=1;i<=n;++i)
    {
                    ciclu=0;
                    for(x=1;x<=n;++x)
                       for(p=G[x];p;p=p->next)
                          if(d[x]<32767)
                            if(d[p->vf]>d[x]+p->cost)
                            {
                                                     d[p->vf]=d[x]+p->cost;
                                                     ciclu=1;
                            }
    }
    ofstream fout("bellmanford.out");
    if(ciclu)
      fout<<"Ciclu negativ!";
    else
      for(i=2;i<=n;++i)
         fout<<d[i]<<' ';
    fout.close();
    return 0;
}
void addarc(short i,short j,short c)
{
     nod *p=new nod;
     p->vf=j;
     p->cost=c;
     p->next=G[i];
     G[i]=p;
}