#include <fstream>
#include <vector>
#define DMAX 50000
#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;
vector <nod> lista[DMAX];
vector <int> C;

int d[DMAX], apare[DMAX];
bool use[DMAX];

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].push_back(aux);
    }
}

void rezolvare()
{
    int i, vfa, vfu;
    int prim=0, ultim=0;
    
    initializare();
    C.push_back(1);
    
    while (prim<=ultim)
    {
        vfa=C[prim++];
        for (i=0; i<lista[vfa].size(); 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.push_back(vfu);
                    ultim++;
                }
                
                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]<< ' ';
}