#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define N 500005
#define inf 0x3f3f3f3f

using namespace std;

int n, m, d[N], nr_aparitii[N];

vector <pair <int , int> >G[N];

queue <int> q;

vector<pair <int , int> >::iterator it;

int prelucrare()
{
    q.push(1);

    int x, tmp;

    while(!q.empty())
    {
        x = q.front();

        q.pop();

        nr_aparitii[x]++;

        if(nr_aparitii[x] > n)
        {
            return 0;
        }

        for(it = G[x].begin() ; it != G[x].end() ; ++it)
        {
            tmp = d[x] + it->first;

            if(tmp < d[it->second])
            {
                d[it->second] = tmp;

                q.push(it->second);
            }
        }
    }

    return 1;
}

void citire()
{
    scanf("%d %d\n",&n,&m);

    int a, b, c;

    for(int i = 0 ; i < m ; ++i)
    {
        scanf("%d %d %d\n",&a,&b,&c);

        G[a].push_back(make_pair(c,b));
    }

    for(int i = 2 ; i <= n ; ++i)
    {
        d[i] = inf;
    }

    if(prelucrare())
    {
        for(int i = 2 ; i <= n ; ++i)
        {
            printf("%d ",d[i]);
        }
    }
    else
    {
        printf("Ciclu negativ!");
    }
}

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

    citire();

    return 0;
}