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