using namespace std;
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50005
#define inf 250000000

FILE *f=fopen ("bellmanford.in","r");
FILE *g=fopen ("bellmanford.out","w");

vector < pair <int,int> > G[NMAX];
queue <int> Q;
bool viz[NMAX],ciclu_neg=false;
int aparitii[NMAX],d[NMAX];

int main()
{
   int n,m,i,x,y,c;

   fscanf(f,"%d%d",&n,&m);

   for(i=1; i<=m; i++)
   {
       fscanf(f,"%d%d%d",&x,&y,&c);
       G[x].push_back(make_pair(y,c));
   }


   d[1]=0;
   viz[1]=1;
 //  aparitii[1]=1;
   Q.push(1);

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

    while(!Q.empty() && !ciclu_neg)
    {
        x=Q.front();
        Q.pop();
        viz[x]=0;

          vector < pair <int,int> >::iterator it;
        for(it=G[x].begin(); it!=G[x].end(); it++)
        {
           if(d[x]<inf) if(d[it->first]>d[x]+it->second)
            {
                 d[it->first]=d[x]+it->second;
                if( !viz[it->first])
                {

                    if(aparitii[it->first]>n)
                    {
                        ciclu_neg=true;
                        continue;
                    }

                    else
                    {
                        aparitii[it->first]++;
                        Q.push(it->first);
                        viz[it->first]=1;
                     }
                }

            }
        }
    }

    if(ciclu_neg) fprintf(g,"Ciclu negativ!");
    else
    for(i=2; i<=n; i++) fprintf(g,"%d ",d[i]);





   return 0;
}