#include <cstdio>
#include <vector>
#include <queue>
#define NMAX 50001
using namespace std;
FILE *fin, *fout;
int n, m, st, cmin[NMAX], prec[NMAX], i;
const int inf=1<<28;
int nr[NMAX];
bool ciclic=0;

struct arc {int vf, c;};

vector <arc> G[NMAX];
queue <int> C;

void citire()
{
    fin=fopen("bellmanford.in", "r"); fout=fopen("bellmanford.out", "w");
    arc crt; int i, x;
    fscanf (fin, "%d%d", &n, &m); st=1;
    for (i=0; i<m; i++) { fscanf (fin, "%d%d%d", &x, &crt.vf, &crt.c); G[x].push_back(crt); }
}

void initializare() {
    int i;
    for (i=1; i<=n; i++) cmin[i]=inf, prec[i]=st;
    prec[st]=0; cmin[st]=0; C.push(st);
}

void rec (int i) {
    if (i!=st) rec(prec[i]);
    fprintf (fout, "%d ", i);
}
int main()
{
    int vf, aux;
    citire();
    initializare();
    while (!C.empty() && !ciclic) {
        vf=C.front(); C.pop();
        for (i=0; i<G[vf].size() && !ciclic; ++i) {
            aux=cmin[vf]+G[vf][i].c;
            if (aux<cmin[G[vf][i].vf]) {
                cmin[G[vf][i].vf]=aux;
                prec[G[vf][i].vf]=vf;
                C.push(G[vf][i].vf);
                ++nr[G[vf][i].vf];
                if (nr[G[vf][i].vf]>=n) ciclic=1; //!!verificare ciclic
            }
        }
    }
    if (ciclic) fprintf (fout, "Ciclu negativ!\n");
    else {
        for (i=2; i<=n; ++i) fprintf (fout, "%d ", cmin[i]);
        fprintf (fout, "\n");
    }
    fclose(fout);
    return 0;
}