#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;
}