#include <vector>
#include <queue>
#include <fstream>
#define NMAX 50001
#define INF 1000000000
using namespace std;
ifstream fin("bellmanford.in ");
ofstream fout("bellmanford.in ");
struct arc {int vf,cost;};
void citire();
void initializare();
void belman();
void afisare();

vector <arc> L[NMAX];
queue <int> C;
//L[x] va fi lista de adiacenta a varfului x

int n,x0=1,Cmin[NMAX],pre[NMAX],Cate[NMAX];

int main()
{
    citire();
    initializare();
    belman();

}
void citire()
{
    int m,i,x,y,co;
    arc aux;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>co;
        aux.vf=y; aux.cost=co;
        L[x].push_back(aux);
    }
}
void initializare()
{
    int i;
    for(i=1;i<=n;i++)  {Cmin[i]=INF;pre[i]=x0;C.push(i);Cate[i]=1;}
    pre[x0]=0; Cmin[x0]=0;
    for(i=0;i<L[x0].size();i++)
        Cmin[L[x0][i].vf]=L[x0][i].cost;
}
void belman()
{
    int sol=1,x,i;
    while(!C.empty()&&sol)
    {
        x=C.front();  C.pop();
        for(i=0;i<L[x].size();i++)
            if(Cmin[L[x][i].vf]>Cmin[x]+L[x][i].cost)
            {
                Cmin[L[x][i].vf]=Cmin[x]+L[x][i].cost;
                C.push(L[x][i].vf);
                Cate[L[x][i].vf]++;
                if(Cate[L[x][i].vf]==n) {sol=0;break;}
                pre[L[x][i].vf]=x;
            }

    }
    if(!sol) fout<<"Ciclu negativ!";
    else
        afisare();
}
void afisare()
{
    int i;
    for(i=2;i<=n;i++) fout<<Cmin[i]<<" ";
}