#include <vector>
#include <queue>
#include <stdio.h>
#define NMAX 50001
#define INF 1000000000
using namespace std;
FILE *fin,*fout;
//ifstream fin("bellmanford.in");
//ofstream fout("bellmanford.out");
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()
{
    fin=fopen("bellmanford.in","r");
    fout=fopen("bellmanford.out","w");
    int m,i,x,y,co;
    arc aux;
    fscanf(fin,"%d%d",&n,&m);
    //fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fscanf(fin,"%d%d%d",&x,&y,&co);
        //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) fprintf(fout,"Ciclu negativ!");
        //fout<<"Ciclu negativ!";
    else
        afisare();
}
void afisare()
{
    int i;
    for(i=2;i<=n;i++) //fout<<Cmin[i]<<" ";
        fprintf(fout,"%d ",Cmin[i]);
}