#include <fstream>
#include <iostream>
#define  inf 10000;
using namespace std;
short a[30000][30000];
short d[30000],tata[30000];
int n,m,x,y,c,i,j,k;
void cit()
{
    ifstream f;
    f.open("bellmanford.in");
    f>>n>>m;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
                a[i][j]=10000;
    for (int i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        a[x][y]=c;
    }
    f.close();
}
bool bf(int x0)
{
    bool ok;
    for (i=1;i<=n;i++)
    {
        d[i]=10000;
        tata[i]=0;
    }
    d[x0]=0;
    for (i=1;i<=n;i++)
    {
        ok=true;
        for (j=1;j<=n;j++)
            for (k=1;k<=n;k++)
            {
                if (d[j]<10000 && a[j][k]<10000)
                {
                    if (d[k]>a[j][k]+d[j])
                    {
                        d[k]=a[j][k]+d[j];
                        ok=false;
                        tata[k]=j;
                    }
                }
            }
    }
    return ok;
}
int main()
{
    cit();
    ofstream g;
    g.open("bellmanford.out");
    if (!bf(1)) g<<"Ciclu negativ!";
    else
    {
        for (i=2;i<=n;i++)
            g<<d[i]<<" ";
    }
    return 0;
}