#include <fstream>
#define inf 100000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int cmin[5000],c[5000][5000];
int n,mc,start;

void citire();
void afisare();
void bellman();

int main()
{
    citire();
    bellman();
    return 0;
}

void citire()
{
    int i,j,x,y,cost;
    fin>>n>>mc;
    start=1;
    for(i=1;i<=mc;i++)
    {
        fin>>x>>y>>cost;
        c[x][y]=cost;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(c[i][j]==0 && i!=j)
                c[i][j]=inf;
    for(i=1;i<=n;i++)
        cmin[i]=c[start][i];
}

void bellman()
{
    int i,j,k,modif=0;
    for(i=1;i<=n;i++)
        cmin[i]=c[start][i];
    for(k=1;k<=n;k++)
    {
        modif=0;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(cmin[j]>cmin[i]+c[i][j])
                {
                    cmin[j]=cmin[i]+c[i][j];
                    modif=1;
                }
    }
    if(modif)
        fout<<"Ciclu negativ!";
    if(!modif)
        afisare();
}

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