#include <fstream>

using namespace std;
struct nod{int inf,cost;
           nod *next;};
typedef nod* lista;
lista aux,lv[50000],p;
int n,m,d[50000],cat[50000];int coada[2500000];
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
void bellman(){d[1]=0;int ok=1;
              for(int i=2;i<=n;i++)d[i]=900000;


                   int prim,ultim;
                   prim=0;
                   ultim=1;
                   coada[ultim]=1;
                   cat[1]++;
                   while(prim<ultim&&ok){int x;
                                     x=coada[++prim];
                                     for(p=lv[x];p;p=p->next)
                                        if(d[p->inf]>d[x]+p->cost){d[p->inf]=d[x]+p->cost;
                                                                     coada[++ultim]=p->inf;
                                                                     cat[p->inf]++;
                                                                     if(cat[p->inf]>n)ok=0;
                                                                     }
                                    }
                    if(!ok)fout<<"Ciclu negativ!\n";
                      else
                for(int i=2;i<=n;i++)fout<<d[i]<<" ";
                }

int main()
{int x,y,c;
fin>>n;
for(int i=1;i<=n;i++)lv[i]=NULL;
fin>>m;
for(int i=1;i<=m;i++)
    {fin>>x>>y>>c;
     aux=new nod;
     aux->inf=y;
     aux->cost=c;
     aux->next=lv[x];
     lv[x]=aux;
    }
bellman();

    return 0;
}