#include <fstream>
#include <queue>
#include <vector>
#define maxn 50001
#define maxm 250001
#define inf 100000000

using namespace std;

vector < pair <int, int> > A[maxn];
int cost[maxn], apare[maxn],n,m;
bool in_coada[maxn];

queue <int> coada;

int main()
{
    int a,b,c,nod,i;
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
    f >> n >> m;
    for (i=1;i<=m;i++)
    {
        f >> a >> b >> c;
        A[a].push_back(make_pair(b,c));
    }
    for (i=1;i<=n;i++)
    {
        cost[i]=inf;
        apare[i]=0;
    }
    cost[1]=0;
    apare[1]=1;
    coada.push(1);
    in_coada[1]=true;
    bool ciclu=false;
    nod = 1;
    while (!ciclu && !coada.empty())
    {
        nod = coada.front();
        coada.pop();
        in_coada[nod]=false;
        for (i=0;i<A[nod].size();i++)
        {
            pair <int, int> q = A[nod][i];
            if (cost[nod]+q.second <cost[q.first])
            {
                cost[q.first]=cost[nod]+q.second;
                if (!in_coada[q.first])
                {
                    if (apare[q.first] > n)
                    {
                        ciclu=true;
                    }
                    else
                    {
                        coada.push(q.first);
                        in_coada[q.first]=true;
                        apare[q.first]++;
                    }
                }
            }
        }
    }
    if (ciclu)
        g << "Ciclu negativ!";
    else
        for (i=2;i<=n;i++)
            g << cost[i] << " ";
    return 0;
}