#include <fstream>
#include <vector>
using namespace std;
ifstream in("bellmanford.in");
ofstream out("bellmanford.out");

vector <int> a[50001],b[50001];
int d[50001],q[2000000],n,m,i,x,y,z,l,k,j;
bool ok;
int main()
{
    in>>n>>m;
    for(i=1;i<=m;i++)
    {
        in>>x>>y>>z;
        a[x].push_back(y);
        b[x].push_back(z);
    }
    l=1; k=1;
    d[1]=0; q[1]=1;
    for(i=2;i<=n;i++) d[i]=10000000;
    while (l<=k)
    {
        x=q[l];
        for(i=0;i<a[x].size();i++)
        {
            y=a[x][i];
            if(d[x]+b[x][i]<d[y])
            {
                k++;
                q[k]=y;
                d[y]=d[x]+b[x][i];
            }
        }
        l++;
    }
    ok=true;
    for(i=1;i<=n;i++)
        for(j=0;j<a[i].size();j++)
        {
            y=a[i][j];
            if(d[i]+b[i][j]<d[y])
            {
                ok=false;
                out<<"Ciclu negativ!";
            }
        }
    if(ok==true)
        for(i=2;i<=n;i++)
            out<<d[i]<<" ";
    return 0;
}