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

using namespace std;

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

struct edge{
  int to;
  int koltseg;
};

int const INF =1e9+7;
int const NMAX =5e4;
int disst[1+NMAX];
int ezsor[1+NMAX];
vector<edge>graf[1+NMAX];

void bellman(int start,int n) {
  for(int i=1;i<=NMAX;i++) {
    disst[i]=INF;
    ezsor[i]=false;
  }
  queue <int> sor;
  disst[start] = 0;
  ezsor[start] = true;
  sor.push(start);
  int index= 1;
  while(index <= n && !sor.empty()) {
    int sormerete= sor.size();
    for(int t = 0;t < sormerete;t++) {
      int from = sor.front();
      sor.pop();
      ezsor[from] = false;
      for(int i = 0;i < graf[from].size();i++) {
        int to =graf[from][i].to;
        if(disst[from] + graf[from][i].koltseg < disst[to]) {
          disst[to] = disst[from] + graf[from][i].koltseg;
          if(!ezsor[to]) {
            ezsor[to] = true;
            sor.push(to);
          }
        }
      }
    }
    index++;
  }
  if(!sor.empty()) fout<<"Ciclu negativ!";
  else {
    for(int i=2;i<=n;i++) fout<<disst[i]<<" ";
  }
}

int main() {
  int n,m;
  fin>>n>>m;
  for(int i=1;i<=m;i++) {
    int a,b,koltseg;
    fin>>a>>b>>koltseg;
    graf[a].push_back({b,koltseg});
  }
  bellman(1,n);
  return 0;
}