#include <bits/stdc++.h>
using namespace std;

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

const int MAXN = 100001;
const int INF = 1e9;
typedef pair<int, int> PII;

int n, m, x, y, z, d[MAXN], rep[MAXN];
priority_queue <PII, vector<PII>, greater<PII>> PQ;
vector <PII> G[MAXN];

void Bellman_Ford(int start) {
  for(int i = 1; i <= n; i++)
    d[i] = INF;

  d[start] = 0;
  PQ.push({0, start});
  
  while(!PQ.empty()) {
    int dist = PQ.top().first;
    int node = PQ.top().second;
    PQ.pop();

    if(dist > d[node])
      continue;

    for(auto nxt : G[node]) {
			rep[nxt.first]++;
			if(rep[nxt.first] > n) {
				fout << "Ciclu negativ\n";
				return;
			}
			
      if(d[nxt.first] > dist + nxt.second) {
        d[nxt.first] = dist + nxt.second;
        PQ.push({d[nxt.first], nxt.first});
      }
		}
  }
}

int main() {
  fin >> n >> m;
  for(int i = 1; i <= m; i++) {
    fin >> x >> y >> z;
    G[x].push_back({y, z});
  }

  Bellman_Ford(1);
  
  for(int i = 2; i <= n; i++)
		fout << (d[i] == INF ? -1 : d[i]) << " ";
	fout << "\n";

  return 0;
}