#include <bits/stdc++.h>
#define in "bellmanford.in"
#define out "bellmanford.out"
#define Nmax 50003
#define oo (1 << 30)
using namespace std;
ifstream fin(in);
ofstream fout(out);

int n,m;
int d[Nmax];
bool viz[Nmax];
int freq[Nmax];
priority_queue <pair<int,int> > q;
vector <pair<int,int> > L[Nmax];

void Read()
{
    int i,x,y,cost;

    fin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        L[x].push_back({y,cost});
    }
}

/// Bellman Ford
void BF()
{
    bool ciclu;
    int i,k,nod,cost;

    /// initializare
    for (i = 1; i <= n; i++)
        d[i] = oo;

    ciclu = false;
    viz[1] = true;
    d[1] = 0;
    freq[1] = 1;
    q.push({1,0});
    while(!q.empty() && !ciclu)
    {
        k = q.top().first;
        q.pop();

        viz[k] = false;
        for (auto i : L[k])
        {
            nod = i.first;
            cost = i.second;
            if (d[nod] > d[k] + cost)
            {
                d[nod] = d[k] + cost;
                ++freq[nod];
                if (freq[nod] > n) ciclu = true;

                if (!viz[nod])
                {
                    viz[nod] = true;
                    q.push({nod,-d[nod]});
                }
            }
        }
    }

    if (ciclu) fout << "Ciclu negativ!";
    else
    {
        int j;
        for (j = 2; j <= n; j++)
            fout << d[j] << " ";
        fout << "\n";
    }
}

int main()
{
    Read();
    BF();

    fin.close();
    fout.close();
    return 0;
}