#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
#include <tuple>
using namespace std;

int N, M;
vector<vector<pair<int,int>>> Graph;
queue<int> Q;
bitset<50005> inQ;
vector<int> queueCount, DP;

void bellmanFord(int k)
{
  DP[k] = 0;
  Q.push(k);
  inQ[k] = true;
  ++queueCount[k];
  int v, cost;
  while (!Q.empty()) {
    k = Q.front(); Q.pop();
    inQ[k] = false;

    if (queueCount[k] > N) {
      printf("Ciclu negativ!\n");
      return;
    }
    
    for (auto it: Graph[k]) {
      tie(v, cost) = it;
      if (DP[v] > DP[k] + cost) {
	DP[v] = DP[k] + cost;
	if (!inQ[v]) {
	  Q.push(v);
	  inQ[v] = true;
	}
	++queueCount[v];
      }
    }
  }
  for (int i = 1; i < N; ++i)
    printf("%d ", DP[i]);
  printf("\n");
}

int main()
{
  freopen("bellmanford.in", "r", stdin);
  freopen("bellmanford.out", "w", stdout);

  scanf("%d%d", &N, &M);
  Graph.resize(N);
  DP.resize(N, 0x3f3f3f3f);
  queueCount.resize(N);
  int from, to, cost;
  for (int i = 0; i < M; ++i) {
    scanf("%d%d%d", &from, &to, &cost);
    --from; -- to;
    Graph[from].emplace_back(to, cost);
  }

  bellmanFord(0);
  
  return 0;
}