#include <fstream>

#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#if __cplusplus > 199711L
#include <unordered_map>
#include <unordered_set>
#endif

#include <cmath>
#include <cstring>
#include <cstdlib>

using namespace std;

const int inf = 0x3f3f3f3f;

int N, M;
int cost[50010], in_num[50010];
vector<pair<int, int> > Graph[50010];
bitset<50010> inside;
queue<int> Q;

int main()
{
    int i, x, y, c, node;
    bool neg_cycle = false;
    vector<pair<int, int> >::iterator it;

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

    fin >> N >> M;

    for (i = 0; i < M; ++i)
    {
        fin >> x >> y >> c;
        Graph[x].push_back(make_pair(y, c));
    }

    memset(cost, inf, sizeof(cost));

    Q.push(1);
    inside[1] = true;
    cost[1] = 0;
    in_num[1] = 1;

    while(!Q.empty() && neg_cycle == false)
    {
        node = Q.front();
        Q.pop();
        inside[node] = false;

        for (it = Graph[node].begin(); it != Graph[node].end(); ++it)
        {
            if (cost[it->first] > cost[node] + it->second)
            {
                cost[it->first] = cost[node] + it->second;

                if (!inside[it->first])
                {
                    if (cost[it->first] < 0 && in_num[it->first] > N)
                        neg_cycle = true;
                    else
                    {
                        inside[it->first] = true;
                        ++in_num[it->first];
                        Q.push(it->first);
                    }
                }
            }
        }
    }

    if (neg_cycle)
        fout << "Ciclu negativ!";
    else
        for (i = 2; i <= N; ++i)
            fout << cost[i] << ' ';

    fout << '\n';
    fout.close();
    return 0;
}