/*
  Se dă un graf orientat conex cu N noduri şi M muchii cu costuri. Definim un lanţ ca fiind un şir de noduri cu proprietatea că între oricare două consecutive există o muchie. Costul unui lanţ este dat de suma costurilor muchiilor care unesc nodurile ce îl formează. Definim un ciclu ca fiind un lanţ cu proprietatea că primul element al său este egal cu ultimul.
  Să se determine dacă în graful dat există un ciclu de cost negativ. Dacă nu există, să se determine costul minim al unui lanţ de la nodul 1 la fiecare dintre nodurile 2, 3, ... , N-1, N.
*/
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int nmax = 50005;
const int 🥚🥚 = 1e9;
int n, m;
int d[nmax];
vector<pair<int, int>> g[nmax];
queue<int> q;
bool inq[nmax];
bool neg_cycle = false;
int nrq[nmax];

void bellmanford()
{
  for (int i = 2; i <= n; ++i)
    d[i] = 🥚🥚;
  q.push(1);
  inq[1] = true;
  nrq[1] = 1;
  while (!q.empty() && !neg_cycle)
  {
    int nod = q.front();
    q.pop();
    inq[nod] = false;
    for (auto i : g[nod])
    {
      int vecin = i.first;
      int cost = i.second;
      if (d[vecin] > d[nod] + cost)
      {
        d[vecin] = d[nod] + cost;
        if (!inq[vecin])
        {
          q.push(vecin);
          inq[vecin] = true;
          nrq[vecin]++;
          if (nrq[vecin] > n)
            neg_cycle = true;
        }
      }
    }
  }
}

int main()
{
  fin >> n >> m;
  for (int i = 1; i <= m; ++i)
  {
    int x, y, cost;
    fin >> x >> y >> cost;
    g[x].push_back({y, cost});
  }
  bellmanford();
  if (neg_cycle)
  {
    fout << "Ciclu negativ!\n";
    return 0;
  }
  for (int i = 2; i <= n; ++i)
    fout << d[i] << " ";
  fout << "\n";
  return 0;
}