#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, nrvf, inapoi, m;

int cmin[NMAX], d[NMAX]; //cmin[x]=costul drumului de cost minim de la start la x

int nr[NMAX]; //nr[x]=de cate ori a fost actualizat costul drumului de cost minim de la start la x

struct varf{int vf, cost;};

vector<varf>G[NMAX];

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<<'\n';

    fout.close();

    return 0;

}



void citire()

{

     int x, y, c, i,j;

     varf aux;

    fin>>n>>m;

    for (x=0; x<m; x++)

   {

        fin>>i>>j>>c;

        aux.vf=j;

        aux.cost=c;

        G[i].push_back(aux);

    }



}



bool bellman_ford()

///returnam 0 daca nu exista solutie

///returnam 1 daca exista solutie

{

    int i, x;

    ///initializare

    for (i=1; i<=n; i++)

        cmin[i]=INF;

    cmin[start]=0;

    C.push(start);

    while (!C.empty())

          {

           x=C.front();

           C.pop();

           ///parcurg lista de adiacenta a lui x

           for (i=0; i<G[x].size(); i++)

               if (cmin[G[x][i].vf]>cmin[x]+G[x][i].cost)

                   {

                    cmin[G[x][i].vf]=cmin[x]+G[x][i].cost;

                    nr[G[x][i].vf]++;

                    if (nr[G[x][i].vf]==n) return 0;

                    C.push(G[x][i].vf);

                   }

          }

    return 1;

}