#include<bits/stdc++.h>

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

const int Nmax = 5e4 + 3;
const int Mmax = 250003;

#define inf 1000000000

struct muchie
{
    long a, b, c;
}e[Mmax];

long n, m, k, cost[Nmax];

long verif_negativ()
{
    for(int i = 1; i <= m; ++i)
        if(cost[e[i].a] + e[i].c < cost[e[i].b])
            return 1;
    return 0;
}

void solve()
{
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            if(cost[e[j].a] + e[j].c < cost[e[j].b])
                cost[e[j].b] = cost[e[j].a] + e[j].c;
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= m; ++i)
        f >> e[i].a >> e[i].b >> e[i].c;

    cost[1] = 0;
    for(int i = 2; i <= n; ++i)
        cost[i] = inf;

    solve();

    if(verif_negativ())
    {
        g << "Ciclu negativ!\n";
        return 0;
    }
    for(int i = 2; i <= n; ++i)
        g << cost[i] << ' ';
    return 0;
}