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

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

struct muchie {
    int nod;
    int cost;
}; muchie make_m(int x, int y) { muchie k; k.nod = x; k.cost = y; return k; }

vector<muchie> adiacenta[50005];

int distanta[50005], viz[50005];

int N, M;
int main()
{
    f >> N >> M;
    for ( int i=1; i<=M; i++ )
    {
        int x;
        muchie m;
        f >> x >> m.nod >> m.cost;

        adiacenta[x].push_back(m);
    }
    memset(distanta, numeric_limits<char>::max(), sizeof distanta);
    distanta[1] = 0;

    for ( int i=1; i<=N-1; i++ )
    {
        for ( int j=1; j<=N; j++ )
            for ( vector<muchie>::iterator it = adiacenta[j].begin(); it != adiacenta[j].end(); it++ )
            {
                int u = j;
                int v = it->nod;
                int cost = it->cost;

                if ( distanta[u] + cost < distanta[v] )
                    distanta[v] = distanta[u]+cost;
            }
    }

    bool cycle = false;
    for ( int j=1; j<=N; j++ )
            for ( vector<muchie>::iterator it = adiacenta[j].begin(); it != adiacenta[j].end(); it++ )
            {
                int u = j;
                int v = it->nod;
                int cost = it->cost;

                if ( distanta[u] + cost < distanta[v] )
                {
                    cycle = true;
                    break;
                }
            }

    if ( cycle == true )
    {
        g << "Ciclu negativ!";
        return 0;
    }
    for ( int i=2; i<=N; i++ )
        g << distanta[i] << ' ';
}