#include <bits/stdc++.h>
#include <cstring>
#define inf 2000000000
#define ss second
#define ff first

using namespace std;


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

int const NMAX = 50001;
int used[NMAX];
int viz[NMAX];
int d[NMAX];
vector < pair <int, int> > v[NMAX];
queue< int > q;
int main() {
  int n, m;
  fin >> n >> m;
  for(int i = 1; i <= m; ++i)
    {
      int nod1, nod2, cost;
      fin >> nod1 >> nod2 >> cost;
      v[nod1].push_back({nod2, cost});
    }
  for(int i = 2; i <= n; ++i)
    d[i] = inf;

  q.push(1);
  used[1] = 1;
  int ok = 1;
  while(!q.empty() && ok == 1)
    {
      int nod = q.front();
      q.pop();
      used[nod] = 0; // nu mai este in coada
      ++viz[nod]; // de cate ori a fost vizitat
      if(viz[nod] > n)
      {
        fout << "Ciclu negativ";
        ok = 0;
      }
      else
      {
        for(auto x : v[nod])
          {
            if(d[x.first] > d[nod] + x.second)
            {
              d[x.first] = d[nod] + x.second;
              if(used[x.first] == 0)
              {
                q.push(x.first);
                used[x.first] = 1;
              }
            }
          }
      }
    }
  if(ok == 1)
  {
  for(int i = 2; i <= n; ++i)
    fout << d[i] << " ";
  }
  return 0;
}