#include <bits/stdc++.h>

using namespace std;

#define cin fin
#define cout fout
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

struct el{
int nod,cost;
};

queue<int> q;
vector<el> a[50001];
int sol[50001],viz[50001],n,m;
bool inq[50001];

void bellman_ford(int start)
{
    q.push(start);
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        inq[x] = 0;
        for (auto y:a[x]){
            if (sol[x] + y.cost < sol[y.nod]){
                sol[y.nod]=sol[x] + y.cost;

                if (inq[y.nod]) continue;

                q.push(y.nod);
                inq[y.nod]=1;

                viz[y.nod]++;
                if (viz[y.nod] >= n)
                {
                    cout << "Ciclu negativ!";
                    exit(0);
                }

            }
        }
    }
}
int main()
{
    cin >> n >> m;
    int x,y,cost;
    for (int i = 1; i <= m; i++)
    {
        cin >> x >> y >> cost;
        a[x].push_back({y,cost});
    }
    for (int i = 2;  i <= n; i++)
    {
        sol[i] = 1e9;
    }
    bellman_ford(1);
    for (int i = 2; i <= n; i++)
    {
        cout << sol[i] << " ";
    }



}