#include<fstream>
#include<vector>
#include<queue>
#define NMAX 50010
#define MMAX 250010
#define INF 250000000

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

struct muchie
{
    int x, c, o;
};

int n, m, nr[MMAX], vz[NMAX], best[NMAX];

vector<muchie> v[NMAX];
queue<int> q;

void Citeste()
{
    int x, y, c, i;
    muchie r;

    f>>n>>m;

    for (i=1; i<=m; ++i)
    {
        f>>x>>y>>c;
        r.c=c; r.o=i;
        r.x=y; v[x].push_back(r);
       // r.x=x; v[y].push_back(r);
    }

    for (i=1; i<=n; ++i) best[i]=INF;
}

void Solve()
{
    int i, gata=0, nod, val;
    muchie r;
    q.push(1); best[1]=0;

    while (!gata && !q.empty())
    {
        nod=q.front(); q.pop();

        for (i=0; i<v[nod].size(); ++i)
        {
            r=v[nod][i];
            val=best[nod]+r.c;

            if (val<best[r.x])
            {
                best[r.x]=val;
                q.push(r.x);
                ++nr[r.o];
                if (nr[r.o]==n)
                {
                    gata=1;
                    break;
                }
            }

        }
    }

    if (gata) g<<"Ciclu negativ!";
    else
        for (i=2; i<=n; ++i) g<<best[i]<<" ";
}

int main()
{
    Citeste();
    Solve();
    f.close();
    g.close();
    return 0;
}