#include<stdio.h>
#include<vector>
#include<queue>
#define maxn 50005
#define inf 999999999
using namespace std;

int uz[maxn],nr[maxn],d[maxn],n,m;

vector <int> l[maxn],lc[maxn];


void cit()
{
    int i,x,y,z;

    scanf("%d %d",&n,&m);

    for(i=1;i<=m;i++)
      {
          scanf("%d %d %d",&x,&y,&z);
          l[x].push_back(y);
          lc[x].push_back(z);
      }

      for(i=1;i<=n;i++)
      d[i]=inf;

      d[1]=0;
}




int bellman()
{
    int k,nrr,i;
    queue <int> q;

    q.push(1); uz[1]=1; nr[1]=1;


    while(!q.empty())
    {
        k=q.front();
        nrr=l[k].size();

        for(i=0;i<nrr;i++)
          if(lc[k][i]+d[k] < d[l[k][i]])
          {
              d[l[k][i]]=lc[k][i]+d[k];

              if(uz[l[k][i]]==0)
              {
                  q.push(l[k][i]);
                  uz[l[k][i]]=1;
                  nr[l[k][i]]++;

                  if(nr[l[k][i]]>n)
                   return 0;
              }
          }

        uz[k]=0;
        q.pop();
    }

    return 1;
}






void afis()
{
    int i;

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





int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);

    cit();
    afis();

    fclose(stdin);
    fclose(stdout);

    return 0;

}