#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>
#define inf=INT_MAX
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
vector < pair <int, int> > L[50001];
int D[50001], S[50001], n, m;
void Citire()
{int i, x, y , c;
    f>>n>>m;
 for(i=1;i<=m;i++)
 {f>>x>>y>>c;
     L[x].push_back(make_pair(y,c));
 }
}
void Bellman_Ford()
{ int i, j, k,ok;
    for(i=1;i<=n;i++)
        D[i]=INT_MAX;
    D[1]=0;
    for(i=1;i<=n;i++)
    { ok=0;
        for(j=1;j<=n;j++)
             for(k=0;k<L[j].size();k++)
               if(D[j]!=INT_MAX&&D[L[j][k].first]>D[j]+L[j][k].second)
                 {
                 D[L[j][k].first]=D[j]+L[j][k].second;
                  S[L[j][k].first]=j;
                  ok=1;
                 }
    }
if(ok==1)
    g<<"Ciclu negativ!";
else  {
        for(i=2;i<=n;i++)
      g<<D[i]<<" ";
      }
}


int main()
{
Citire();

Bellman_Ford();

f.close();
g.close();
    return 0;
}