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

#define nmax 50010
#define pb push_back
#define mp make_pair
#define to first
#define cost second

vector< pair<long, long> >nodes[nmax];
vector<long> distances(nmax,10000),app(nmax);
vector<bool> InQueue(nmax);
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);
                     nodes[x].pb(mp(y,c));
     }
}


int BellmanFord()
{
     distances[1]=0;
     queue<long> q;
     q.push(1);
     InQueue[1]=true;
     app[1]=1;
     vector< pair<long,long> >::iterator it;
     while(!q.empty())
     {
                      int nod=q.front();
                      q.pop();
                      InQueue[nod]=false;
                      if(app[nod]>n)
                      {
                                    return 1;
                      }
                      for(it=nodes[nod].begin();it!=nodes[nod].end();++it)
                      {
                              if(distances[it->to]>distances[nod]+it->cost)
                              {
                                         distances[it->to]=distances[nod]+it->cost;
                                         if(InQueue[it->to]==false)
                                         {
                                                    q.push(it->to);
                                                    app[it->to]++;
                                                    InQueue[it->to]=true;
                                         }
                              }
                      }
     }                                             
     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;
}