#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

const int INF = 0x3f3f3f3f;

using namespace std;

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

class Edge {
public:
  int to() const {return to_;}
  int cost() const {return cost_;}
  Edge() = default;
  Edge(int to, int cost): to_(to), cost_(cost) {}
private:
  int to_;
  int cost_;
};

vector<vector<Edge>> Graph;

void bellmanFord(int k, int N) {
  vector<int> DP, timesInQueue;
  vector<bool> inQueue;
  queue<int> Q;
  
  timesInQueue.resize(N);
  inQueue.resize(N);

  DP.resize(N);
  fill(DP.begin(), DP.end(), INF);
  DP[k] = 0;

  Q.push(k);
  inQueue[k] = true;
  timesInQueue[k] = 1;

  while (!Q.empty()) {
    k = Q.front(); Q.pop();
    inQueue[k] = false;
    for (auto edge: Graph[k])
      if (DP[edge.to()] > DP[k] + edge.cost()) {
	DP[edge.to()] = DP[k] + edge.cost();
	if (inQueue[edge.to()])
	  continue;
	inQueue[edge.to()] = true;
	timesInQueue[edge.to()] += 1;
	Q.push(edge.to());
	if (timesInQueue[edge.to()] > N) {
	  fout << "Ciclu negativ!\n";
	  exit(0);
	}
      }
  }
  for (int i = 1; i < N; ++i)
    fout << DP[i] << " ";
  fout << "\n";
}

int main()
{

  int N, M;
  fin >> N >> M;
  Graph.resize(N);

  int from, to, cost;
  for (int i = 0; i < M; ++i) {
    fin >> from >> to >> cost;
    --from; --to;
    Graph[from].emplace_back(to, cost);
  }

  bellmanFord(0, N);
  
  return 0;
}