#include <bits/stdc++.h>
#define INF 1000000008
#define NMAX 50008

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

struct Muchie
{
    int vf, c;
};

struct comparare
{
    bool operator() (const Muchie & a, const Muchie & b)
    {
        return a.c > b.c;
    }
};

int n, m, start = 1;
int dmin[NMAX], pre[NMAX], nr[NMAX];
bool uz[NMAX];
vector <Muchie> G[NMAX];
priority_queue <Muchie, vector<Muchie>, comparare> H;

void Dijkstra();
void BellmanFord();

int main()
{
    int x, y, z;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> z;
        G[x].push_back({y, z});
    }
    BellmanFord();
    return 0;
}

void BellmanFord()
{
    bool negativ = 0;
    queue <int> Q;
    vector <Muchie> :: iterator it;
    for (int i = 1; i <= n; i++)
        dmin[i] = INF;
    dmin[start] = 0;
    Q.push(start);
    while (!Q.empty() && !negativ)
    {
        int x = Q.front();
        Q.pop();
        for(it = G[x].begin(); it != G[x].end(); it++)
            if (dmin[it->vf] > dmin[x] + it->c)
            {
                dmin[it->vf] = dmin[x] + it->c;
                nr[it->vf]++;
                Q.push(it->vf);
                if (nr[it->vf] > n)
                    negativ = 1;
            }

    }

    if (negativ == 1)
        fout << "Ciclu negativ!";

    for (int i = 2; i <= n; i++)
    {
        if (dmin[i] == INF)
            dmin[i] = 0;
        fout << dmin[i] << ' ';
    }
}