#include <fstream>
#include <vector>
#define NMAX 1000
#define INF 50051001

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct varf
      {
       int vf, c;
      };

int n, m, prim, ultim, start=1, existasol;
varf G[NMAX][NMAX];
int prec[NMAX], nr[NMAX], C[NMAX], dmin[NMAX], gr[NMAX];

void citire();
void bellmanford();

int main()
{int i;
 citire();
 bellmanford();
 if (existasol==0)
     fout<<"Ciclu negativ!"<<'\n';
     else
     for (i=1; i<=n; i++)
          if (i!=start)
              fout<<dmin[i]<<' ';
 return 0;
 fin.close();
 fout.close();
}


void citire()
    {int i, x, y, cost;
     fin>>n>>m;
     for (i=0; i<m; i++)
          {fin>>x>>y>>cost;
           G[x][gr[x]].vf=y;
           G[x][gr[x]].c=cost;
           gr[x]++;
          }
     C[0]=start;
     for (i=1; i<=n; i++)
          {nr[i]=0; prec[i]=start;
           dmin[i]=INF;
          }
     dmin[start]=0; prec[start]=0; existasol=1;
    }


void bellmanford()
    {int i, y, x;
     while (prim<=ultim && existasol==1)
            {x=C[prim]; prim++;
             for (i=0; i<gr[x]; i++)
                  {y=G[x][i].vf;
                   if (dmin[y]>dmin[x]+G[x][i].c)
                       {dmin[y]=dmin[x]+G[x][i].c;
                        prec[y]=x; nr[y]++;
                        if (nr[y]==n)
                            {existasol=0;
                             break;
                            }
                        ultim++; C[ultim]=y;
                       }
                  }
            }
    }