#include <fstream>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct bf{int u,v,w;};
bf v[50001];
bool neg=false;
int n,m,i,j,w[50001],p[50001];

int main()
{
    fin>>n>>m;
    for (i=2;i<=n;i++)
    {
        w[i]=1<<30;
    }
    for (i=1;i<=m;i++)
    {
        fin>>v[i].u>>v[i].v>>v[i].w;
    }
    //formarea drumului;
    //O(N*M);
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            if (w[v[j].u]+v[j].w<w[v[j].v])
            {
                w[v[j].v]=w[v[j].u]+v[j].w;
                p[v[j].v]=v[j].u;
            }
        }
    }
    //pentru cicluri negative;
    for (j=1;j<=m;j++)
    {
        if (w[v[j].u]+v[j].w<w[v[j].v])
            fout<<"Ciclu negativ!",neg = true;
    }
    if (neg == false)
    for (i=2;i<=n;i++)
    {
        fout<<w[i]<<" ";
    }
    return 0;
}