#include <cstdio>
#include <vector>
#include <queue>
#define NMAX 50010
#define INF 2000000000
using namespace std;

int dmin[NMAX];
int counter[NMAX];
int n, m, cicluosesteosnegativuossinuamunossolutiones;
vector < pair<int, int> > L[NMAX];

void citire();
void Bellman_Ford();
void afisare();

int main()
{
    citire();
    Bellman_Ford();
    afisare();
    return 0;
}

void citire()
{
    int i;
    int a, b, c;
    FILE*fin=fopen ("bellmanford.in", "r");
    fscanf (fin, "%d %d", &n, &m);
    for (i=1; i<=m; ++i)
    {
        fscanf (fin, "%d %d %d", &a, &b, &c);
        L[a].push_back (make_pair (b, c));
    }
    fclose(fin);
    return;
}

void Bellman_Ford()
{
    int i, p, j;
    queue <int> Q;
    Q.push(1);//primul varf
    counter[1]=1;
    for (i=2; i<=n; ++i)
        dmin[i]=INF;
    while (!Q.empty())
    {
        p=Q.front();
        Q.pop();
        if (counter[p]>=n)
            cicluosesteosnegativuossinuamunossolutiones=1;
        for (j=0; j<L[p].size(); ++j)
            if (dmin[L[p][j].first]>dmin[p]+L[p][j].second)
        {
                dmin[L[p][j].first]=dmin[p]+L[p][j].second;
                Q.push(L[p][j].first);
                ++counter[L[p][j].first];
        }
    }
    return;
}

void afisare()
{
    int i;
    FILE*fout=fopen ("bellmanford.out", "w");
    if (cicluosesteosnegativuossinuamunossolutiones)
        fprintf(fout, "Ciclu negativ!");
        else
        for (i=2; i<=n; ++i)
            fprintf (fout, "%d ", dmin[i]);
    fprintf (fout, "\n");
    fclose(fout);
    return;
}