#include <iostream>
#include <cstdlib>
#include <fstream>
#include <cstring>
#include <limits>
#include <vector>
#include <queue>
#include <set>

#define INF std::numeric_limits<int >::max()
#define MAXN 50005
#define MAXM 50005
#define START 1

using namespace std;
ifstream f("bellmanford.in" );
ofstream g("bellmanford.out");

int MinDist[MAXN], N, M;

vector< std::pair<int, int> > Adiacenta[MAXN];
queue<int> coada;

int viz[MAXN];
int vizQ[MAXN];

int main(int argc, char **argv)
{
    f >> N >> M;

    for ( int i=1, x, y, z; i<=M; i++)
    {
        f >> x >> y >> z;
        Adiacenta[x].push_back( std::make_pair(y, z) );
    }

    for ( int i=1; i<=N; i++ ) MinDist[i] = INF;
    MinDist[START] = 0;
    vizQ[START] = 1;
    coada.push(1);

    while ( !coada.empty() )
    {
        int node = coada.front();
        coada.pop();
        vizQ[node] = 0;

        if ( MinDist[node] == INF ) continue;

        for ( std::vector< std::pair<int, int> >::iterator it = Adiacenta[node].begin(); it!=Adiacenta[node].end(); ++it )
        {
            int vecin = it->first;

            if ( MinDist[node] + it->second < MinDist[vecin] )
            {
                MinDist[vecin] = MinDist[node] + it->second;
                if ( vizQ[vecin] == 0 ) {
                    coada.push(vecin);
                    vizQ[vecin] = 1;
                    viz[vecin]++;
                }
                if ( viz[vecin] > N )
                {
                    g << "Ciclu negativ!";
                    return 0;
                }
            }
        }
    }

    for ( int i=2; i<=N; i++ )
        g << (MinDist[i]==INF?0:MinDist[i]) << ' ';
}