#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
using namespace std;

#define nmax 50010
#define pb push_back


struct other
{
       long cost,end;
};

struct edge
{
       vector<other> neighbour;
};

edge nodes[nmax];
vector<long> distances(nmax,10000);
long n,m,x,y,c;


void read_input()
{
     scanf("%ld %ld", &n,&m);
     for(int i=0;i<m;i++)
     {
                     scanf("%ld %ld %ld", &x,&y,&c);
                     other New;
                     New.end=y;
                     New.cost=c;
                     nodes[x].neighbour.pb(New);
     }
}


int BellmanFord()
{
     distances[1]=0;
     for(int i=1;i<n;i++)
     {
             for(int j=1;j<=n;j++)
             {
                  for(int k=0;k<nodes[j].neighbour.size();k++)
                  {
                          long start=j;
                          long end=nodes[j].neighbour[k].end;
                          if(distances[start]+nodes[j].neighbour[k].cost<distances[end])
                          {
                                          distances[end]=distances[start]+nodes[j].neighbour[k].cost;
                          }                                          
                  }
             }   
     }
     for(int i=1;i<n;i++)
     {
             for(int j=1;j<=n;j++)
             {
                     for(int k=0;k<nodes[j].neighbour.size();k++)
                     {
                          long start=j;
                          long end=nodes[j].neighbour[k].end;
                          if(distances[start]+nodes[j].neighbour[k].cost<distances[end])
                          {
                                  return 1;                                                      
                          } 
                     }
             }
     }
     return 0;
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
   // int i;
    read_input();
    if(BellmanFord()==1) printf("Ciclu negativ!\n");
    else for(int i=2;i<=n;i++) printf("%ld ", distances[i]);
    //scanf("%i", &i);
    return 0;
}