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