#include <bits/stdc++.h>
#define LIM 1000000001

using namespace std;

const int nmax=50005;

vector <pair <int, int> > g[nmax];
priority_queue < pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > heap;

int c[nmax];
int nr_passed[nmax];
int n, m;

bool mod;

void bellman_ford(int start_node)
{
    for(int i=1;i<=n;i++)
        c[i]=LIM;
    c[start_node]=0;
    heap.push({c[start_node], start_node});
    while(heap.size())
    {
        int nod=heap.top().second;
        int cost=heap.top().first;
        nr_passed[nod]++;
        if(nr_passed[nod]==n)
        {
            mod=true;
            break;
        }
        if(cost<=c[nod])
        {
            for(int i=0;i<g[nod].size();i++)
            {
                int c_nod=g[nod][i].first;
                int c_cost=g[nod][i].second;
                if(c[c_nod]>cost+c_cost)
                {
                    c[c_nod]=cost+c_cost;
                    heap.push({c[c_nod], c_nod});
                }
            }
        }
    }
}

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

    scanf("%d%d", &n, &m);
    for(int i=1;i<=m;i++)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        g[x].push_back({y, c});
    }
    bellman_ford(1);
    mod=false;
    if(mod==true)
        printf("Ciclu negativ!");
    else
        for(int i=2;i<=n;i++)
            printf("%d ", c[i]);
    printf("\n");

    return 0;
}