#include <iostream>
#include <fstream>
#define oo 199999999
using namespace std;

int a[9000][9000], coada[9000], distante[9000], vizitat[9000], qfront, qback;

ifstream f("bellmanford.in");
ofstream fout("bellmanford.out");
int bellman_ford(int start, int n)
{
    int i, nod;
    for(i=1; i<=n; i++)
        distante[i]=oo;
    distante[start]=0;
    vizitat[start]=1;

    qfront=1; qback=0;
    coada[++qback]=start; // diferenta dintre i++ si ++i o vezi aici http://stackoverflow.com/questions/24853/what-is-the-difference-between-i-and-i

    while(qfront<=qback)
    {
        nod=coada[qfront];
        qfront++;

        vizitat[nod]++;    // habar nu am ce fac liniile astea
        if(vizitat[nod]>n)
            return 0;

        for(i=1; i<=n; i++)
            if(a[nod][i]!=0)
                if(distante[i]>distante[nod]+a[nod][i])
                {
                    distante[i]=distante[nod]+a[nod][i];
                    coada[++qback]=i;
                }
    }
    return 1;
}
int main()
{
    int n, m, i=0, x, y, cost;
    f >> n >> m; // m numarul de muchii !!! am facut pe orientat
    while(i<m)
    {
        f >> x >> y >> cost;
        a[x][y]=cost;
        i++;
    }

    if(bellman_ford(1, n))
        for(i=2; i<=n; i++)
            fout << distante[i] << " ";
    else
        fout << "Ciclu negativ!";

    return 0;
}