#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
#include <bitset>

using namespace std;

const int N = 50005, oo = 1e9;

vector <pair <int, int> > L[N];
vector <int> cnt(N), d(N);
bitset <N> inq;
queue <int> q;
int n;

void Read ()
{
    ifstream fin ("bellmanford.in");
    int m;
    fin >> n >> m;
    while (m--)
    {
        int x, y, c;
        fin >> x >> y >> c;
        L[x].push_back({y, c});
    }
}

void BellmanFord ()
{
    for (int i = 2; i <= n; i++)
        d[i] = oo;
    inq[1] = 1;
    cnt[1] = 1;
    q.push(1);
    bool Negative_Cycle = 0;
    while (!q.empty() && !Negative_Cycle)
    {
        int vertex = q.front();
        q.pop();
        inq[vertex] = 0;
        for (auto next : L[vertex])
            if (d[next.first] > d[vertex] + next.second)
            {
                if (cnt[next.first] > n) Negative_Cycle = 1;
                d[next.first] = d[vertex] + next.second;
                if (!inq[next.first])
                {
                    inq[next.first] = 1;
                    cnt[next.first]++;
                    q.push(next.first);
                }
            }
    }
    ofstream fout ("bellmanford.out");
    if (Negative_Cycle) fout << "Ciclu negativ!\n";
    else for (int i = 2; i <= n; i++)
        fout << d[i] << " ";
    fout << "\n";
    fout.close();
}

int main()
{
    Read();
    BellmanFord();
    return 0;
}