#include <bits/stdc++.h>
#define x first
#define y second

using namespace std;

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

vector < pair < int, int > > v[100005];

queue < pair < int , int > > q;

int n, m, i, a, b, s, fvup[100005], fv[100005], c;

pair <int, int> aux;

int main ()
{
    fin>>n>>m;

    for ( i = 1; i <= m ; i++ )
    {
        fin>>a>>b>>c;

        v[a].push_back( {b, c} );

    }

    q.push( { 1 , 0 } );

    fv[1] = -1;

    while (!q.empty())
    {
        aux = q.front();
        q.pop();

        fvup[aux.x]++;

        if ( fvup[aux.x] > n )
        {
            fout<<"Ciclu negativ!";
            return 0;
        }

        if ( fv[aux.x] <= aux.y )
        {
            continue;
        }

        fv[aux.x] = aux.y;


        for ( i = 0 ; i < v[aux.x].size() ; i++ )
        {
            q.push( { v[aux.x][i].x , aux.y + v[aux.x][i].y } );
        }

    }

    for ( i = 2 ; i <= n; i++ )
    {
        fout<<fv[i]<<" ";
    }

    return 0;
}