#include <fstream>
#define DMAX 100 // trebuie schimbat!!
#define INFINIT 999999
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

void citire();
void rezolvare();
void initializare();
void afisare();

struct nod
{
    int vf, cost;
};

int n, m;
nod lista[DMAX][DMAX];

int C[DMAX*DMAX];
int d[DMAX], apare[DMAX];
bool use[DMAX];
//NU AM NEVOIE DE P PENTURU CA NU TREBUIE SA RECONSTRUIESC DRUMUL

int main()
{
    citire();
    rezolvare();
    
    fin.close();
    fout.close();
    return 0;
}

void citire()
{
    int i, x;
    nod aux;
    
    fin>> n>> m;
    for (i=1; i<=m; i++)
    {
        fin>> x>> aux.vf>> aux.cost;
        lista[x][++lista[x][0].vf]=aux;
    }
}

void rezolvare()
{
    int i, vfa, vfu;
    int prim=0, ultim=0;
    
    initializare();
    C[ultim]=1;
    
    while (prim<=ultim)
    {
        vfa=C[prim++];
        for (i=1; i<=lista[vfa][0].vf; i++)
        {
            vfu=lista[vfa][i].vf;
            if (d[vfu]>d[vfa]+lista[vfa][i].cost)
            {
                d[vfu]=d[vfa]+lista[vfa][i].cost;
                if (!use[vfu])
                {
                    C[++ultim]=vfu;
                    
                    apare[vfu]++;
                    if (apare[vfu]>n)
                    {
                        fout<<"Ciclu negativ!";
                        return;
                    }
                }
            }
        }
    }
    
    afisare();
}

void initializare()
{
    int i;
    for (i=1; i<=n; i++) d[i]=INFINIT, use[i]=0, apare[i]=0;
    d[1]=0;
    use[1]=1;
    apare[1]=1;
}

void afisare()
{
    int i;
    for (i=2; i<=n; i++)
        fout<< d[i]<< ' ';
}