#include <bits/stdc++.h>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");
int n,m,d[50001],f[50001];
struct muchie
{ int nod,cost;
};
vector <muchie> v[50001];
queue <int> q;
int main()
{ in>>n>>m;
  for(int i=1;i<=m;i++)
  { int x,y,c;
    in>>x>>y>>c;
    v[x].push_back({y,c});
  }
  for(int i=2;i<=n;i++)
    d[i]=1<<30;
  q.push(1);
  while(!q.empty())
  { int x=q.front();
    q.pop();
    f[x]++;
    if(f[x]>n)
    { out<<"Ciclu negativ!";
      in.close();
      out.close();
      return 0;
    }
    for(auto it: v[x])
      if(d[it.nod]>d[x]+it.cost)
         d[it.nod]=d[x]+it.cost,q.push(it.nod);
  }
  for(int i=1;i<=n;i++)
    if(d[i]==1<<30)
       d[i]=0;
  for(int i=2;i<=n;i++)
    out<<d[i]<<" ";
  out<<'\n';
  in.close();
  out.close();
  return 0;
}