#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50004
#define MMAX 250004
#define INF 1000000

using namespace std;

ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

int n, m;
int d[NMAX];

struct muchie {int v, cost;};//vecinul si costul
vector <muchie> vecini[NMAX];//lista de muchii incidente cu fiecare varf
queue <int> C;//coada
bool uz[NMAX];//daca este in coada
int viz[NMAX];//de cate ori a fost in coada

void citire();
bool bellman_ford();
void afisare();

int main()
{
    citire();
    if(!bellman_ford())
        fout<<"Ciclu negativ!";
        else
            afisare();

    return 0;
}

void citire()
{
    int i, u;
    muchie mc;

    fin>>n>>m;

    for(i=2;i<=n;++i)
        d[i]=INF;

    for(i=1;i<=m;++i)
    {
        fin>>u>>mc.v>>mc.cost;
        vecini[u].push_back(mc);
    }
}

bool bellman_ford()
{
    int crt, vec, nrv, vecbun;

    C.push(1); uz[1]=1; viz[1]=1;

    while(!C.empty())
    {
        crt=C.front(); C.pop(); uz[crt]=0;

        nrv=vecini[crt].size();
        for(vec=0;vec<nrv;++vec)
            if(d[vecini[crt][vec].v]>d[crt]+vecini[crt][vec].cost)
            {
                vecbun=vecini[crt][vec].v;
                d[vecbun]=d[crt]+vecini[crt][vec].cost;

                if(!uz[vecbun])
                {
                    C.push(vecbun);
                    uz[vecbun]=1;
                    ++viz[vecbun];

                    if(viz[vecbun]>n)
                        return 0;
                }
            }
    }

    return 1;
}

void afisare()
{
    int i;

    for(i=2;i<=n;++i)
        fout<<d[i]<<' ';
    fout<<'\n';
}

/*
FARA COADA

int n, m;
int d[NMAX];
struct {int v1, v2;
        int cost;} muchie[MMAX];

void citire();
bool bellman_ford();
void afisare();

int main()
{
    citire();
    if(!bellman_ford())
        fout<<"Ciclu negativ!";
        else
            afisare();

    return 0;
}

void citire()
{
    int i;

    fin>>n>>m;

    for(i=2;i<=n;++i)
        d[i]=INF;

    for(i=1;i<=m;++i)
    {
        fin>>muchie[i].v1>>muchie[i].v2>>muchie[i].cost;
        if(muchie[i].v1==1)
            d[muchie[i].v2]=muchie[i].cost;
    }
}

bool bellman_ford()
{
    int vf, mc;

    for(vf=1;vf<=n;++vf)
        for(mc=1;mc<=m;++mc)
            if(d[muchie[mc].v2]>d[muchie[mc].v1]+muchie[mc].cost)
                d[muchie[mc].v2]=d[muchie[mc].v1]+muchie[mc].cost;

    for(mc=1;mc<=m;++mc)
        if(d[muchie[mc].v2]>d[muchie[mc].v1]+muchie[mc].cost)
            return 0;

    return 1;
}

void afisare()
{
    int i;

    for(i=2;i<=n;++i)
        fout<<d[i]<<' ';
    fout<<'\n';
}*/