#include <bits/stdc++.h>
#define dim 250002
#define int long long
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout("bellmanford.out");
const int inf=100000000000;
int n,sol[dim],viz[dim];
bool inq[dim];

struct el
{
    int nod,cost;
};
queue<int>coada;
vector<el> a[dim];

void bellmanford ()
{
    while (!coada.empty())
    {
        int x=coada.front();
        coada.pop();
        inq[x] = false;

        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;

                coada.push(y.nod);
                inq[y.nod] = true;

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

            }
    }
}

void Solve ()
{
    int i,m,x,y,z;
    fin>>n>>m;
    for (i=2; i<=n; i++)
        sol[i] = inf;
    while (m--)
    {
        fin>>x>>y>>z;
        a[x].push_back({y,z});
    }
    coada.push(1);
    bellmanford();
    for (i=2;i<=n;i++)
        fout<<sol[i]<<' ';
}

int32_t main()
{
    int t=1;
    while (t--)
    {
        Solve();
    }
    return 0;
}