#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#define Nmax 50069
#define MAX 999999999
using namespace std;
vector <pair<int,int> >G[Nmax];
vector <pair<int,int> >::iterator it;
queue <int> C;
int n,dmin[Nmax],nr[Nmax];
void reading(int &n)
{
    int i,m,x,y,z;
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d %d %d",&x,&y,&z);
        G[x].push_back(make_pair(y,z));
    }
}
void bellmanford()
{
   int x,i;
   bool stop=false;
   for(i=1;i<=n;++i) {dmin[i]=MAX;nr[i]=0;}
   C.push(1);dmin[1]=0;
   while(!C.empty() && !stop)
   {
       x=C.front();C.pop();
       for(it=G[x].begin();it!=G[x].end();++it)
       if (dmin[it->first]>dmin[x]+it->second)
       {
             dmin[it->first]=dmin[x]+it->second;
             C.push(it->first);
             ++nr[it->first];
             if (nr[it->first]>n) stop=true;
       }

   }
   if (stop) printf("Ciclu negativ!");
   else
   {
       for(i=2;i<=n;++i)
       printf("%d ",dmin[i]);
   }
}
int main()
{
    reading(n);
    bellmanford();
    return 0;
}