#include <fstream>
#include <queue>
#include <vector>
#define NMAX 50005
#define INF 1000000000

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

void citire();
bool bellman_ford();

int n,m,start=1;
struct varf {int x; int c;};
vector <varf> G[NMAX];
queue <int> C;
int cmin[NMAX];///costul drumului de cost minim de la start la x
int nr[NMAX];///de cate ori a fost actualizat costul minim de la start la i


int main ()
{
 int i;
 citire();
 if (!bellman_ford())
    fout<<"Ciclu negativ!";
    else
        for (i=2;i<=n;i++)
            if (cmin[i]==INF) fout<<"-1"<<' ';
             else fout<<cmin[i]<<' ';
 return 0;
}
void citire()
{
 int i,j,c,k;
 varf aux;
 fin>>n>>m;;
 for (k=0;k<m;k++)
     {
      fin>>i>>j>>c;
      aux.x=j;aux.c=c;
      ///j intra in lista de adiacenta a lui i
      G[i].push_back(aux);
     }
}
bool bellman_ford()///0 nu exista sol, 1 exista sol
{
 int i,vf;
 ///intializare
 for (i=1;i<=n;i++) cmin[i]=INF;
 cmin[start]=0;
 C.push(start);
 while (!C.empty())
     {
      vf=C.front();
      C.pop();
      ///parcurg lista de adiacenta a lui x
      for (i=0;i<G[vf].size();i++)
          if (cmin[G[vf][i].x]>cmin[vf]+G[vf][i].c)
              {
               cmin[G[vf][i].x]=cmin[vf]+G[vf][i].c;
               nr[G[vf][i].x]++;
               if (nr[G[vf][i].x]==n) return 0;
               C.push(G[vf][i].x);
              }
     }
 return 1;
}