#include <iostream>
#include<fstream>
#define inf 100000000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,i,cst[250001],v[50001],j;
bool ok;
struct muchie
{
    int x,y;
};
muchie c[250001];
int functie(int i,int j,int c)
{
    if(v[j]>v[i]+c)
    {
        v[j]=v[i]+c;
        //parrent[j]=i;
        return 1;
    }
    return 0;
}
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>c[i].x>>c[i].y>>cst[i];
    }
    v[1]=0;
    for(i=2;i<=n;i++)
        v[i]=inf;
    for(i=1;i<n;i++)
        for(j=1;j<=m;j++)
    {
        functie(c[j].x,c[j].y,cst[j]);
    }
    ok=1;
    for(j=1;j<=m && ok;j++)
    {
        int x1=v[c[j].y];
        if(functie(c[j].x,c[j].y,cst[j]))
            g<<"Ciclu negativ!",ok=0,v[c[j].y]=x1;
    }
    if(ok)
        for(i=2;i<=n;i++)
        g<<v[i]<<' ';
}