#include <stdlib.h>
#include <queue>
#include <bitset>
#include <vector>
#include <fstream>
#define INF 2147000000
#define MAXN 50002
#define MAXM 250002
using namespace std;
vector <pair <int,int> > graf[MAXN];
int d[MAXN], count[MAXM];
bitset <MAXN> inqueue;
queue<int> Q;


int main(){
  int n,m,i,x,y,c,nod,fiu;
  bool cycle=false;
  vector<pair<int,int> >::iterator it;

  ifstream f("bellmanford.in");
  ofstream g("bellmanford.out");

  f>>n>>m;
  for (i=1;i<=m;++i){
    {
    f>>x>>y>>c;
    graf[x].push_back(make_pair(y,c));
    }

  }

  for (i=2;i<=n;++i)d[i]=INF;
  for (i=1;i<=n;i++) count[i]=0;

  d[1]=0; Q.push(1); inqueue[1]=1;

  while (!Q.empty() && (!cycle)){
    nod=Q.front(); Q.pop(); inqueue[nod]=0;
    for (it=graf[nod].begin();it!=graf[nod].end();it++)
        {
        fiu=it->first;
        if (d[nod]+(it->second)<d[fiu])
            {
            d[fiu]=d[nod]+(it->second);
            if (inqueue[fiu]==0)
                {
                if (count[fiu]>n) cycle=true;
                else
                    {
                    Q.push(fiu);
                    inqueue.flip(fiu);
                    count[fiu]++;
                    }
                }
            }
        }
  }
   if (!cycle)
    for (i=2;i<=n;++i) g<<d[i]<<" ";
    else g<<"Ciclu negativ!\n";

return 0;
}