#include <cstdio>
#include <vector>
#define INF 2000000000
#define NMAX 50005
#define MMAX 250005

using namespace std;

FILE *fin=fopen("bellmanford.in","r");
FILE *fout=fopen("bellmanford.out","w");

struct pereche
{
int vf,cost;
};

int n,m,negativ;
vector<pereche> LG[NMAX];
vector<int> Q;
char inQ[NMAX];
int vizQ[NMAX];
long long int d[NMAX];

void citire();
void init();
void rezolvare();
void afisare();

int main()
{
citire();
init();
rezolvare();
afisare();
    return 0;
}

void citire()
{
int i,j,x,y,c;
pereche A;
//fin>>n>>m;
fscanf(fin,"%d %d",&n,&m);
for (i=1;i<=m;i++)
     {
     fscanf(fin,"%d %d %d",&x,&y,&c);
     A.vf=y;
     A.cost=c;
     LG[x].push_back(A);
     }
}

void init()
{
int i;
for (i=2;i<=n;i++)
    d[i]=INF;
Q.push_back(1);
inQ[1]=1;
vizQ[1]=1;
}

void rezolvare()
{
int prim=0,z,y;
while (!Q.empty())
       {
        y=Q[prim++];
        for (z=0;z<LG[y].size();z++)
             if (d[z]>d[y]+LG[y][z].cost)
                {
                 d[z]=d[y]+LG[y][z].cost;
                 if (inQ[z]==0)
                    {
                     inQ[z]=1;

                    }
                }
       }
}

void afisare()
{
int i;
if (negativ==1)
    {fprintf(fout,"Ciclu negativ!\n");
     return;
    }
for (i=2;i<=n;i++)
     fprintf(fout,"%d ",&d[i]);
     //fout<<d[i]<<' ';
fprintf(fout,"\n");
//fout<<'\n';
}