#include <fstream>
#include <queue>

using namespace std;

ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

const int Nmax=50005;
const int Mmax=250005;
queue <int> q;

int vf[Mmax],lst[Nmax],urm[Mmax],cost[Mmax],d[Nmax],nrq[Nmax];
int n,m,a,b,c,nr,cazul;
bool inq[Nmax];

void adauga ( int x , int y , int c )
{
    nr++;
    vf[nr]=y;
    cost[nr]=c;
    urm[nr]=lst[x];
    lst[x]=nr;
}

bool bellmanford ( int x )
{

    int p,u,poz,y,nod;

    for ( int i=2 ; i<=n ; i++ )
        d[i]=999999;

    q.push(x);
    inq[x] = true;
    nrq[x] = 1;

    while ( !q.empty() )
    {

        nod=q.front();
        q.pop();
        inq[nod]=false;
        poz=lst[nod];


        while ( poz != 0 )
        {
            y=vf[poz];
            c=cost[poz];

            if ( d[nod] + c < d[y] )
            {
                d[y]=d[nod]+c;

                if ( !inq[y] )
                {
                    q.push(y);
                    inq[y]=true;
                    nrq[y]++;

                    if ( nrq[y] == n )
                        return false;
                }
            }

            poz=urm[poz];
        }

    }
    return true;
}

int main()
{
    fin>>n>>m;
    for ( int i=1 ; i<=m ; i++ )
    {
        fin>>a>>b>>c;
        adauga(a,b,c);
    }

    if ( !bellmanford(1) )
        fout<<"Ciclu negativ!";
    else{
        for ( int i=2 ; i<=n ; i++ )
            fout<<d[i]<<' ';
    }

}