/*
    Algoritmul Bellman-Ford.
    Implementarea algoritmului nu difera cu mult de cautarea în lătime ( bfs )
    Diferenţele sunt
    când scoţi din coadă marchezi nodul ca vizitat
    actualizezi distanţa până la vecini chiar daca vecinul e vizitat
    pentru a determina dacă exista cicluri negative se foloseşte un vector cu numarul de aparţii a fiecarui nod. Daca numarul de apariţii depaseşte nr de noduri atunci avem ciclu negativ

*/
#include<cstdio>
#include<fstream>
#define INFINIT 2100000000 // o valoare foarte mare
using namespace std;

struct nod
{
    int capat, cost;
    nod *next;
};

nod *G[50002];//graful memorat prin listă de adiacenţă
int n, m,
    d[50002],// d[i] - distanţa minimă de la nodul 1 la nodul i
    v[50002];// vector de vizitaţi

void AddArc(int x, int y, int c)//adaug arc de la x la y de cost c
{
    nod *p = new nod;
    p->capat = y;
    p->cost = c;
    p->next = G[x];
    G[x] = p;
}

void citire()
{
    int i;
    ifstream fin("bellmanford.in");
    fin>>n>>m;
    for(i = 1; i <= m ; i++)
    {
        int x, y, c;
        fin>>x>>y>>c;
        AddArc(x, y, c);
    }
}

int bmf(int start)// Bellman-Ford. Funcţia returnează 0 dacă exită ciclu negativ şi 1 dacă nu există
{
    int aparitii[50002], // aparitii[i] - numarul de apariţii ale nodului i in coadă
        i , j, c;
    nod *st, *dr;//coada

    for(i = 1; i <= n; i++)
    {
        d[i] = INFINIT;
        v[i] = 0;
        aparitii[i]=0;
    }
    st=dr=new nod;
    st->capat=start;
    st->next=NULL;

    d[start] = 0;
    v[start] = 1;
    aparitii[i]++;

    while(st)
    {
        i = st->capat; // i - nodul actual
        v[i] = 0;
        for( nod *p = G[i] ; p!=NULL; p=p->next )
        {
            j = p->capat; // j - nod vecin cu i
            c = p->cost;  // c - costul arcului de la i la j

            if( d[j] > d[i]+c) // dacă costul drumului trebuie actualizat
            {
                d[j] = d[i]+c; // actualizez distanţa indiferent dacă j e vizitat sau nu

                if( v[j]==0 ) // doar dacă j este nevizitat îl adaug în coadă
                {
                    v[j]=1;// şi il marchez ca vizitat
                    if(aparitii[j] > n) // dacă nr de aparţii a lui j depăseşte n atunci avem ciclu negativ
                        return 0;
                    aparitii[j]++;

                    nod *t=new nod; // adaug pe j în coadă
                    t->capat=j;
                    t->next=NULL;
                    dr->next=t;
                    dr=dr->next;
                }
            }
        }
        nod *t=st;//sterg primul emement din coadă
        st=st->next;
        delete t;
    }

    return 1; // dacă am ajuns la acest punct atunci înseamnă că nu există cicluri negative
}

int main()
{
    freopen("bellmanford.out", "w", stdout);
    citire();

    if(bmf(1)==0)
        printf("Ciclu negativ!\n");
    else
        for(int i = 2 ; i<=n ; i++ )// afişez distanţele minime
            printf("%d ", d[i] );
    return 0;
}