#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
int N, M, fr[50010], Sol[50010];
vector < pair < int, int > > V[50010];
queue < int > Q;

int main()
{
    fin >> N >> M;
    for (int i = 1, x, y, c; i <= M; i++)
    {
        fin >> x >> y >> c;
        V[x].push_back( { y, c } );
    }

    memset(Sol, 1, sizeof(Sol));
    Sol[1] = 0;
    Q.push(1);

    while (!Q.empty())
    {
        int i = Q.front();
        Q.pop();
        fr[i] += 1;
        if (fr[i] == N)
        {
            fout << "Ciclu negativ!\n";
            fout.close();
            return 0;
        }

        for (vector < pair < int, int > > :: iterator it = V[i].begin(); it != V[i].end(); it++)
        {
            if (Sol[i] + it->second < Sol[it->first])
            {
                Sol[it->first] = Sol[i] + it->second;
                Q.push(it->first);
            }
        }
    }

    for (int i = 2; i <= N; i++) {
        fout << Sol[i] << ' ';
    }

    fout << '\n';
    fout.close();
    return 0;
}