#include <fstream>
#include <vector>
#include <queue>
#include <climits>

#define NMAX 50005

using namespace std;

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

int n, m, x, y, cost;
int answer[NMAX], timesInQueue[NMAX];
bool inQueue[NMAX];
vector <pair <int, int> > v[NMAX];
queue <int> que;

bool bellmanFord() {
    que.push(1);
    inQueue[1] = true;
    timesInQueue[1] = 1;

    while (!que.empty()) {
        int node = que.front();
        que.pop();

        for (auto neighbour : v[node]) {

            if (answer[node] + neighbour.second < answer[neighbour.first]) {
                answer[neighbour.first] = answer[node] + neighbour.second;

                if (!inQueue[neighbour.first]) {
                    que.push(neighbour.first);
                    inQueue[neighbour.first] = true;
                    timesInQueue[neighbour.first]++;

                    if (timesInQueue[neighbour.first] == n)
                        return 0;
                }
            }
        }

        inQueue[node] = false;
    }

    return 1;
}

int main()
{
    f >> n >> m;
    for (int i = 1; i <= m; i++) {
        f >> x >> y >> cost;

        v[x].push_back({y, cost});
    }

    for (int i = 2; i <= n; i++)
        answer[i] = INT_MAX;

    if (!bellmanFord()) {
        g << "Ciclu negativ!" << "\n";
        return 0;
    }

    for (int i = 2; i <= n; i++)
        g << answer[i] << " ";
    g << "\n";

    return 0;
}