using namespace std;

#include <set>
#include <map>
#include <list>
#include <deque>
#include <stack>
#include <queue>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <utility>
#include <iomanip>
#include <fstream>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>

#define oo (1<<30)
#define f first
#define s second
#define II inline
#define db double
#define ll long long
#define pb push_back
#define mp make_pair
#define Size(V) ((ll)(V.size()))
#define all(V) (V).begin() , (V).end()
#define CC(V) memset((V),0,sizeof((V)))
#define CP(A,B) memcpy((A),(B),sizeof((B)))
#define FOR(i,a,b) for(ll (i)=(a);(i)<=(b);++(i))
#define REP(i, N) for (ll (i)=0;(i)<(ll)(N);++(i))
#define FORit(it, x) for (__typeof((x).begin()) it = (x).begin(); it != (x).end(); ++it)
#define printll(x) printf("%lld",(x))
#define printsp() printf(" ")
#define newline() printf("\n")
#define readll(x) scanf("%lld",&(x))
#define debugll(x) fprintf(stderr,"%lld\n",(x))

#define IN "bellmanford.in"
#define OUT "bellmanford.out"

#define ONLINE_JUDGE

struct edge
{
  int h;
  int t;
  int w;
};

typedef struct edge edge;

int nodeCount;
int edgeCount;

int* minDistances;

edge* edges;

void initStructures()
{
  minDistances = new int[nodeCount + 1];

  minDistances[1] = 0;
  for (int i = 2; i <= nodeCount; i++)
  {
    minDistances[i] = oo;
  }
  edges = new edge[edgeCount];
}

void readGraph()
{
  for (int i = 0; i < edgeCount; i++)
  {
    cin >> edges[i].h >> edges[i].t >> edges[i].w;
  } 
}

bool findshortestPath()
{
  for (int i = 0; i < nodeCount; i++)
  {
    for (int j = 0; j < edgeCount; j++)
    { 
      edge e = edges[j];
      if (minDistances[e.t] > minDistances[e.h] + e.w)
      {
        minDistances[e.t] = minDistances[e.h] + e.w;
      }
    }
    for (int j = 0; j < edgeCount; j++)
    { 
      edge e = edges[j];
      if (minDistances[e.t] > minDistances[e.h] + e.w)
      {

        cout << "Ciclu negativ!";
        return false;
      }
    }
  } 
  return true;
}

void outputSolution()
{
  for (int i = 2; i <=nodeCount; i++)
  {
    cout << minDistances[i] << " ";
  }
}

void solve(int test) {
  cin >> nodeCount >> edgeCount;
  initStructures();
  readGraph();  
  if (findshortestPath())
  {
    outputSolution();
  }
}

int main() {
#ifndef ONLINE_JUDGE
  freopen(IN,"r",stdin);
  freopen(OUT,"w",stdout);
#endif
    solve(1);
  return 0;
}