#include <fstream>
#define NMAX 50010
#define Inf 250000000

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct graf
{
    int neighbour, price;
    graf *next;
};

graf *v[NMAX];
int Q[NMAX], f[NMAX], use[NMAX], n, m, c[50005], ciclu;

void read();
void add(int x, int y, int cost);
void bellmanford();
void afisare();

int main()
{
    read();
    bellmanford();
    afisare();
    return 0;
}

void read()
{
    int i, a, b, d;
    fin >> n >> m;
    for(i = 1; i <= m; i++)
    {
        fin >> a >> b >> d;
        add(a, b, d);
    }
    c[1] = 0;
    for(i = 2; i <= n; i++)
        c[i] = Inf;
}

void add(int x, int y, int cost)
{
    graf *p = new graf;
    p -> neighbour = y;
    p -> price = cost;
    p -> next = v[x];
    v[x] = p;
}

void afisare()
{
    if(ciclu == 0)
    {
    int i;
    for(i = 2; i <= n; i++)
        fout << c[i] << ' ';
    fout << '\n';
    }
    else fout << "Ciclu negativ!"<< '\n';
}

void bellmanford()
{
    int p, u, x;
    graf *nod = new graf;
    p = u = 1;
    Q[p] = 1;
    while(p <= u)
    {
        x = Q[p];
        ++p;
        for(nod = v[x]; nod != NULL; nod = nod->next)
        {
            if(c[nod->neighbour] > nod->price + c[x])
                c[nod->neighbour] = nod->price + c[x];
            if(!use[nod->neighbour])
            {
                use[nod->neighbour] = 1;
                Q[++u] = nod ->neighbour;
            }
            f[nod->neighbour]++;
            if(f[nod->neighbour] == n)
            {
                ciclu = 1;
                return;
            }
        }
        //use[x] = 0;
    }
}