#include <fstream>
#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 {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';
}