#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define INF ~(1<<31)

using namespace std;

struct vecin
{
    int nod, c;
    vecin(int x = 0, int y = 0)
    {
        nod = x;
        c = y;
    }
};

vector<vecin> vec[50010];
queue<int> q;

int n;
int viz[50010], cost[50010], nrm[50010];

void citire()
{
    int m, i, x, y, c;
    scanf("%d%d", &n, &m);
    for(i = 0; i < m; i++)
    {
        scanf("%d%d%d", &x, &y, &c);
        vec[x].push_back(vecin(y, c));
    }
    for(i = 2; i <= n; i++)
        cost[i] = INF;
}

void solve()
{
    q.push(1);
    viz[1] = 1;
    int crt, aux, i;
    vecin nou;

    while(!q.empty())
    {
        crt = q.front();
        q.pop();
        viz[crt] = 0;
        for(i = 0; i < vec[crt].size(); i++)
        {
            nou = vec[crt][i];
            if(cost[nou.nod] > cost[crt] + nou.c)
            {
                cost[nou.nod] = cost[crt] + nou.c;
                if(!viz[nou.nod])
                {
                    q.push(nou.nod);
                    viz[nou.nod] = 1;
                }
                nrm[nou.nod] ++;
                if(nrm[nou.nod] > n)
                {
                    printf("Ciclu negativ!");
                    return;
                }
            }
        }
    }
    //AfIsAre
    for(i = 2; i <= n; i++)
        printf("%d ", cost[i]);
    printf("\n");
}

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    citire();
    solve();

    return 0;
}