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

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

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

queue<int> C;

void citire();
bool bellman_ford();

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]<<' ';
 fout.close();
 return 0;
}

void citire()
{int i, j, c, m, 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()
///returnam 0 daca nu exista solutie
///1 daca exista solutie
{int i, vf;
///initializare
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 vf
      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;
}