#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <limits.h>
#define inf 50005
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m, d[inf], s[inf];
vector <pair <int, int> > v[inf];
queue <int> q;

void citire()
{
    int i,j,c,k;
    f>>n>>m;
    for(k=1; k<=m; k++)
    {
        f>>i>>j>>c;
        v[i].push_back({j,c});
    }
}

int bellman_ford(int start)
{
    int i, poz, nod, cost;
    for(i=1; i<=n; i++)
        d[i]=INT_MAX;
    q.push(start);
    d[start]=0;
    while(!q.empty())
    {
        poz=q.front();
        q.pop();
        s[poz]++;
        if(s[poz]>=n)
            return 0;
        for(i=0; i<v[poz].size(); i++)
        {
            nod=v[poz][i].first;
            cost=v[poz][i].second;
            if(d[nod]>d[poz]+cost)
                {d[nod]=d[poz]+cost; q.push(nod);}
        }
    }
    return 1;
}

int main()
{
    citire();
    if(bellman_ford(1))
        for(int i=2; i<=n; i++)
        g<<d[i]<<" ";
    else
        g<<"Ciclu negativ!";
    f.close();
    g.close();
    return 0;
}