#include <queue>
#include <fstream>
#include <vector>

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

const int Nmax = 50005, oo = 10000000;
int n, m, D[Nmax], nr[Nmax], inq[Nmax], cn;
vector <pair <int, int> > G[Nmax];
queue <int> Q;

void BF()
{
    Q.push(1);
    D[1] = 0;
    while(!Q.empty())
    {
        int nod = Q.front();
        Q.pop();
        for(int i = 0; i <(int)G[nod].size(); i++)
        {
            int vecin = G[nod][i].first, cost = G[nod][i].second;
            if(D[vecin] > D[nod]+cost)
            {
                D[vecin] = D[nod]+cost;
                if(!inq[vecin])
                {
                    inq[vecin] = 1;
                    nr[vecin]++;
                    Q.push(vecin);
                    if(nr[vecin] > n)
                    {
                        cn = 1;
                        return;
                    }
                }
            }
        }
        inq[nod] = 0;
    }
}

int main()
{
    f>>n>>m;
    for(int i = 1; i <= n; i++) D[i] = oo;
    while(m--)
    {
        int x, y, c;
        f>>x>>y>>c;
        G[x].push_back(make_pair(y,c));
    }
    BF();
    if(cn) g<<"Ciclu negativ!\n";
    else for(int i = 2; i <= n; i++)
        g<<D[i]<<' ';
    g<<'\n';
    return 0;
}