#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>

#define Mm 250005
#define Nm 50004
#define INF (int)1e9+2;

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct Graf
{
    int a, b, c;
};

Graf e[Mm];

vector <long long> v[Nm];
vector <pair<int, int> > h;

int cost[Nm], f[Nm];
int n, m;

void Init()
{
    long long i;
    cost[1] = 0;
    for (i = 2; i <= n; i++)
        cost[i] = INF;
    h.push_back(make_pair(0, 1));
    make_heap(h.begin(), h.end());
}

void Solve()
{
    pair<int, int> per;
    int j, nod, poz;
    long long pas = 0;
    while (h.size() && pas <= 1LL * n * m)
    {
        pas++;
        pop_heap(h.begin(), h.end());
        per = h.back();
        h.pop_back();
        nod = per.second;
        f[nod] = 0;
        for (j = 0; j < v[nod].size(); j++)
        {
            poz = v[nod][j];
            if (cost[e[poz].a] + e[poz].c < cost[e[poz].b])
            {
                cost[e[poz].b] = e[poz].c + cost[e[poz].a];
                if(!f[e[poz].b])
                {
                    f[e[poz].b] = 1;
                    h.push_back(make_pair(-cost[e[poz].b], e[poz].b));
                    push_heap(h.begin(), h.end());
                }
            }
        }
    }
}

bool Negative()
{
    int i;
    for (i = 1; i <= m; i++)
        if (cost[e[i].a] + e[i].c < cost[e[i].b])
            return true;
    return false;
}

int main()
{
    int i;
    fin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        fin >> e[i].a >> e[i].b >> e[i].c;
        v[e[i].a].push_back(i);
    }
    Init();
    Solve();
    if (Negative())
    {
        fout << "Ciclu negativ!\n";
        return 0;
    }
    for (i = 2; i <= n; i++)
        fout << cost[i] << " ";
    return 0;
}