#include <fstream>
#define DMAX 5000
#define INFINIT 100000000
using namespace std;

ofstream fout("bellmanford.out");

int n, m, vf_start;
int tata[DMAX];
int Cmin[DMAX];
int C[DMAX][DMAX];
short int M[DMAX];

void citire();
void init();
void dijkstra();
void BellmanFord();
void afisare();

int main()
{
    citire();
    init();
    BellmanFord();
    fout.close();
    return 0;
}

void citire()
{
    ifstream fin("bellmanford.in");

    fin >> n >> m;
    vf_start = 1;


    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            C[i][j] = INFINIT;
            C[i][i] = 0;
        }
    }

    int i,x,y,c;
    for(i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        C[x][y] = c;
    }

    fin.close();
}

void init()
{
    M[vf_start] = 1;
    int i;
    for(i = 1; i <= n; i++)
    {
        Cmin[i] = C[vf_start][i];
        tata[i] = vf_start;
    }
    tata[vf_start] = 0;
}

int minim()
{
    int res = 0, vfmin = 0;
    int i = 1;

    for(i = 1; i <= n; i++)
    {
        if(M[i] == 0 )
        {
            res = Cmin[i];
            vfmin = i;
            break;
        }
    }

    for(i; i <= n; i++)
    {
        if(Cmin[i] < res && M[i] == 0 )
        {
            res = Cmin[i];
            vfmin = i;
        }
    }

    M[vfmin] = 1;

    return vfmin;
}

void dijkstra()
{
    int i, x, vfmin;
    for(i = 1; i <= n-1; i++)
    {
        vfmin = minim();

        for(x = 1; x <= n; x++)
        {
            if(M[x] == 0 && Cmin[x] > Cmin[vfmin] + C[vfmin][x])
            {
                Cmin[x] = Cmin[vfmin] + C[vfmin][x];
                tata[x] = vfmin;
            }
        }
    }
}

void BellmanFord()
{
    bool optim = false;
    int i,x,y;
    for(i = 1; i <= n; i++)
    {
        optim = false;
        for(x = 1; x <= n; x++)
        {
            for(y = 1; y <= n; y++)
            {
                if(Cmin[x] + C[x][y] < Cmin[y])
                {
                    Cmin[y] = Cmin[x] + C[x][y];
                    tata[y] = x;
                    optim = true;
                }
            }
        }
    }
    if(optim) fout << "Ciclu negativ!";
    else afisare();
}

void afisare()
{
    int i;
    for(i = 2; i <= n; i++)
    {
        fout << Cmin[i] << ' ';
    }
}