#include <fstream>
#include <string.h>

#define max_n 50001
#define max_m 250001
#define INF 1<<20

using namespace std;

int i,n,m;
int e[max_m][3],t[max_n],d[max_n];
bool ok1;

ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

void bellman() {
   int i,j,c,z,k;
   bool ok;
   memset(t,0,sizeof(t));
   for (i=1; i<=n; i++) d[i]=1<<20;
   d[1]=0;
   ok=true;
   for (z=1; ok && z<=n; z++)
      for (ok=false, k=1; k<=m; k++) {
          i=e[k][0];
          j=e[k][1];
          c=e[k][2];
          if (d[j]>d[i]+c) {
             d[j]=d[i]+c;
             t[j]=i;
             ok=true;
          }
      }
      for (k=1; k<=m; k++)
          if (d[j]>d[i]+c) {
             out << "Ciclu negativ!" << '\n';
             ok1=false;
             return;
          }
}

int main () {
    in >> n >> m;
    for (i=1; i<=m; i++)
        in >> e[i][0] >> e[i][1] >> e[i][2];
    ok1=true;
    bellman();
    if (ok1)
    for (i=2; i<n; i++) out << d[i] << ' ';
    out << d[n] << '\n';
    return 0;

}