#include <bits/stdc++.h>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

const int NMAX=50005;
const int INF=200000000;

int D[NMAX];

typedef pair < int, int > Pair;

vector < Pair > Ad[NMAX];

priority_queue < Pair, vector < Pair >, greater < Pair > > P;

int source=1;
int n,m;
int viz[NMAX];
int ok;

void read()
{
  int x,y,c;
  fin>>n>>m;
  for(int i=1;i<=m;++i)
  {
      fin>>x>>y>>c;
      Ad[x].push_back(make_pair(y,c));
  }
}

void dij()
{
  int w,u,cost;
  for(int i=1;i<=n;++i) D[i]=INF;

  P.push(make_pair(0,source));
  D[source]=0;

  while(!P.empty())
  {
      u=P.top().second;
      P.pop();

      if(viz[u]==n) {ok=1; return;}

      viz[u]++;

      for(int i=0; i<Ad[u].size(); ++i)
      {
          w=Ad[u][i].first;
          cost=Ad[u][i].second;

          if(D[u]+cost<D[w])
          {
              D[w]=D[u]+cost;

              P.push(make_pair(D[w],w));
          }
      }
  }

}


int main()
{
    read();
    dij();
    if(ok==1) {fout<<"Ciclu negativ!"; return 0;}
    for(int i=2;i<=n;++i) if(D[i]==INF) fout<<0<<" "; else fout<<D[i]<<" ";
    return 0;
}