#include <cstdio>
#include <queue>
#define inf (1<<29)
#define N 50000
using namespace std;
struct Nod{
          int nod,cost;
          Nod *urm;
          }*l[N];
int d[N],circneg,viz[N],n,contor[N];
void read()
{
freopen("bellmanford.in","r",stdin);
int x,y,i,cost,m;
Nod *p;
scanf("%d%d",&n,&m);
while (m--)
   {
   scanf("%d%d%d",&x,&y,&cost);
   p=new Nod;p->nod=y;p->cost=cost;p->urm=l[x];l[x]=p;
   }
}
void BF()
{
int i,k,c;
Nod *p;
queue <int> q;
for (i=1;i<=n;i++) d[i]=inf;
d[1]=0;viz[1]=1;
q.push(1);
while (!q.empty() && !circneg)
   {
   k=q.front();q.pop();
   viz[k]=0;
   for (p=l[k];p!=NULL;p=p->urm)
      {
      i=p->nod;
      c=p->cost;
      if (d[k]<inf)
        if (d[i]>d[k]+c)
           {
           d[i]=d[k]+c;
           if (!viz[i]) if (contor[i]>n) circneg=1;
                        else {
                             q.push(i);
                             viz[i]=1;
                             contor[i]++;
                             }
           }
      }
   }
}
void afis()
{
freopen("bellmanford.out","w",stdout);
if (!circneg)
   {
    for (int i=2;i<=n;i++)
    printf("%d ",d[i]);
   }
else printf("Ciclu negativ!");
}
int main()
{
read();
BF();
afis();
}