#include<bits/stdc++.h>

#define NMAX 50001
#define INF 0x3f3f3f3f

#define pb push_back
#define mp make_pair
#define nod first
#define cost second

using namespace std;

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

vector< pair <int, int > > G[NMAX];
vector< pair <int, int > >::iterator Vecin;
queue <int> Q;
int n, m, x, y, c, Nod;
int D[NMAX], ItNod[NMAX];
bool USED[NMAX];

int main()
{
    f>>n>>m;
    for(int i = 1; i <= m; i++)
    {
        f>>x>>y>>c;
        G[x].pb( mp(y, c) );
    }

    memset(USED, false, sizeof(USED));
    memset(D, INF, sizeof(D));
    memset(ItNod, 0, sizeof(ItNod));

    D[1] = 0;
    Q.push(1);
    USED[1] = true;

    while(!Q.empty())
    {
        Nod = Q.front();
        Q.pop();
        USED[Nod] = 1;

        for( Vecin = G[Nod].begin(); Vecin != G[Nod].end(); Vecin++)
        {
            if( D[(*Vecin).nod] > D[Nod] + (*Vecin).cost ) // minimizam dist pana la acestia
            {
                D[(*Vecin).nod] = D[Nod] + (*Vecin).cost;
                if(!USED[(*Vecin).nod]) // daca nodul ( copilul nodul Nod ) nu se afla in coada
                {
                    Q.push((*Vecin).nod);
                    USED[(*Vecin).nod] = true;
                    if(++ItNod[(*Vecin).nod] > n) // daca s-a trecut de mai mult de N ori prin el
                    {
                        g<<"Ciclu negativ";
                        return 0;
                    }
                }
            }
        }

    }


    for(int i = 2; i <= n; i++)
        g<<D[i]<<" ";
    return 0;
}