#include <vector>
#include <cstdio>
#include <utility>
#include <queue>
#define N 50001

using namespace std;
vector<pair<int,int> > b[N];
queue<int> q;
int cost[N];

int main ()
{freopen("bellmanford.in","r",stdin);
 freopen("bellmanford.out","w",stdout);
 int n,m,x,y,z,i,j,p,aux;
 scanf("%d %d",&n,&m);
 memset(cost,0x7f,sizeof(*cost)*(n+1));
 
 for (i=1;i<=m;i++)
 {scanf("%d %d %d",&x,&y,&z);
  b[x].push_back(make_pair(y,z));
 }
 cost[1]=0;
 q.push(1);
 q.push(-1);
 
 for (i=2;i<=n;i++)
 {while(q.front()!=-1)
  {for (j=0;j<b[(p=q.front())].size();j++)
   {if((aux=cost[p]+b[p][j].second)<cost[b[p][j].first])
    {cost[b[p][j].first]=aux;
     q.push(b[p][j].first);
    }
   }
   q.pop();
  }
  q.pop();
  q.push(-1);
 }
 for (i=1;i<=n;i++)
 {for (j=0;j<b[i].size();j++)
  {if(cost[i]+b[i][j].second<cost[b[i][j].first])
   {printf("Ciclu negativ!");
    return 0;
   }
  }
 }
 
 for(i=2;i<=n;i++)
 {printf("%d ",cost[i]);
 }
 return 0;
}