#include <bits/stdc++.h>
#define MAX 0x3f3f3f3f

using namespace std;

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

class Graf
{
private:
  int N;
  vector<vector<pair<int, int>>> adj;
  vector<int> dist, vizite;

public:
  Graf(int);
  void adaugaMuchie(int, int, int);
  void Dijkstra(int);
};

Graf ::Graf(int n)
{
  N = n;
  vizite.resize(N + 1);
  adj.resize(N + 1);
  dist.resize(N + 1);
}

void Graf :: adaugaMuchie(int x, int y, int w)
{
  adj[x].push_back(make_pair(y, w));
}

void Graf ::Dijkstra(int x)
{
  int i;
  for (i = 1; i <= N; i++)
    dist[i] = MAX;
  dist[x] = 0;
  priority_queue<pair<int, int>> q;
  q.push(make_pair(0, x));
  while (!q.empty())
  {
    int nod = q.top().second;
    q.pop();
    vizite[nod]++;
    if (vizite[nod] == N)
      {
        fout<<"Ciclu negativ!";
        return;
      }
    for (auto curr : adj[nod])
    {
      if (dist[nod] + curr.second < dist[curr.first])
      {
        dist[curr.first] = dist[nod] + curr.second;
        q.push(make_pair(-dist[curr.first], curr.first));
      }
    }
  }
  for (i = 2; i <= N; i++)
    if (dist[i] != MAX)
      fout <<dist[i]<<" ";
    else fout<<0<<" ";
}

int main()
{
  int i, n, m, x, y, w;
  fin >> n >> m;
  Graf G(n);
  for (i = 1; i <= m; i++)
  {
    fin >>x>>y>>w;
    G.adaugaMuchie(x, y, w);
  }
  G.Dijkstra(1);
  return 0;
}