#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
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;
     queue<long> q;
     q.push(1);
     while(!q.empty())
     {
                      int nod=q.front();
                      q.pop();
                      for(int i=0;i<nodes[nod].neighbour.size();i++)
                      {
                              long start=nod;
                              long end=nodes[nod].neighbour[i].end;
                              if(distances[nod]+nodes[nod].neighbour[i].cost<distances[end])
                              {
                                         distances[end]=distances[nod]+nodes[nod].neighbour[i].cost;
                                         q.push(end);
                              }
                      } 
     }                                             
     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;
}