#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define nod first
#define cost second
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
int N, M, fr[50010], A[50010];
vector < pair < int, int > > V[50010];
queue < int > Q;

int main()
{
    fin >> N >> M;
    for (int i=1, a, b, c; i<=M; i++)
    {
        fin >> a >> b >> c;
        V[a].push_back(make_pair(b, c));
    }
    for (int i=1; i<=N; i++) A[i] = 200000000;

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

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

    for (int i=2; i<=N; i++)
    {
        fout << A[i] << ' ';
    }
    fout << '\n';
    fout.close();
    return 0;
}