#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

#define Nmax 50005
#define INF 0x3f3f3f3f

class node
{
    public:

        node( int a, int b )
        {
            this->vecin = a;
            this->cost = b;
        }

        int vecin;
        int cost;
};

vector <node> G[Nmax];
vector <bool> in_queue(Nmax, false);
vector <int> dist(Nmax, INF), cnt_in_queue(Nmax, 0);

queue <int> Q;

int N, M;
bool negative_cycle = false;

void read()
{
    ifstream f("bellmanford.in");

    f >> N >> M;

    for ( int i = 1, a, b, c; i <= M; ++i )
    {
        f >> a >> b >> c;

        node x = { b, c };

        G[a].push_back( x );
    }

    f.close();
}

void BellmanFord()
{
    dist[1] = 0;
    Q.push( 1 );
    in_queue[1] = 1;

    while( !Q.empty() && !negative_cycle )
    {
        int cr = Q.front();
        Q.pop();

        in_queue[cr] = false;

        for ( unsigned i = 0; i < G[cr].size(); ++i )
                if ( dist[cr] < INF )
                {
                    if ( dist[ G[cr][i].vecin ] > dist[cr] + G[cr][i].cost )
                    {
                        dist[ G[cr][i].vecin ] = dist[cr] + G[cr][i].cost;

                        if ( !in_queue[ G[cr][i].vecin ] )
                        {
                            if ( cnt_in_queue[ G[cr][i].vecin ] > N )
                                    negative_cycle = true;
                            else
                            {
                                Q.push( G[cr][i].vecin );
                                in_queue[ G[cr][i].vecin ] = true;
                                cnt_in_queue[ G[cr][i].vecin ]++;
                            }
                        }
                    }
                }
    }
}

void print()
{
    ofstream g("bellmanford.out");

    if ( negative_cycle )
    {
         g << "Ciclu negativ!\n";
    }
    else
    {
        for ( int i = 2; i <= N; ++i )
            g << dist[i] << " ";
    }

    g.close();
}

int main()
{
    read();
    BellmanFord();
    print();

    return 0;
}