/*
Keep it simple
*/

#include <fstream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

#define f first
#define s second
#define INF 2000000000

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

queue <int> Q;
vector < pair < pair < int , int > , int > > v[50010];
pair < pair< int , int > , int > qty;
int i,j,n,m,c,x,y,ans[50010],ok,curPoz,curSiz,curAsc,curCost;

int main()
{
    fin>>n>>m;
    for(i=1 ; i<=m ; ++i)
    {
        fin>>x>>y>>c;
        qty.f.f = y;
        qty.f.s = c;
        v[ x ].push_back( qty );
    }

    for(i=2 ; i<=n ; ++i)
        ans[ i ] = INF;

    Q.push( 1 );
    while( !Q.empty() )
    {
        curPoz = Q.front();
        curSiz = v[ curPoz ].size();
        for(i=0 ; i<curSiz ; ++i)
        {
            curAsc = v[ curPoz ][ i ].f.f;
            curCost = v[ curPoz ][ i ].f.s;
            if( ans[ curAsc ] > ans[ curPoz ] + curCost )
            {
                ans[ curAsc ] = ans[ curPoz ] + curCost;
                v[ curPoz ][ i ].s = v[ curPoz ][ i ].s + 1;
                Q.push( curAsc );
                if( v[ curPoz ][ i ].s >= n )
                {
                    fout<<"Ciclu negativ!";
                    return 0;
                }
            }
        }


        Q.pop();
    }
    for(i=2 ; i<=n ; ++i)
        fout<<ans[ i ]<<' ';

    return 0;
}