#include <cstdio>
#include <vector>
#include <cstring>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define INF 1<<30
#define MX 50005
using namespace std;
vector < pair <int,int> > G[MX];
vector < pair <int,int> > :: iterator it;
int dist[MX],q[MX],x,y,cst,m,n,nod,fr[MX],p,ul,i;
bool u[MX],negativ=false;
void bellman()
{
    while(p<=ul)
    {
        nod=q[p];
        u[nod]=true;
        for( it=G[nod].begin() ; it!=G[nod].end(); it++)
        {
            if(dist[(*it).F]>dist[nod]+(*it).S) dist[(*it).F]=dist[nod]+(*it).S;
            if(!u[(*it).F])
            {
                q[++ul]=(*it).F;
                fr[(*it).F]++;
                if(fr[(*it).F]>n)
                {
                     negativ=true;
                     return;
                }
                u[(*it).F]=true;
            }

        }
        p++;
        u[q[p]]=false;
    }
}
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d",&n,&m);
   for(int w=1;w<=n;w++)
   {
       dist[w]=INF;
   }
    while(m--)
    {
        scanf("%d %d %d",&x,&y,&cst);
        G[x].PB(MP(y,cst));
    }

    dist[1]=0;
    p=ul=1;
    q[1]=1;
  bellman();
  if(negativ)
  {
      printf("Ciclu negativ!");
  }
  else
    for(i=2;i<=n;i++)
    {
        printf("%d ",dist[i]);
    }

    return 0;
}