#include <bits/stdc++.h>
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

const int INF = 1e9;
int n, m;
vector <pair<int, int>> g[50001];

bool cycle = false;
int dist[50001];

void bellman_ford(int source)
{
    bool in_queue[50001];
    int nr_noduri[50001];

    for (int node = 1; node <= n; node++)
    {
        dist[node] = INF;
        in_queue[node] = false;
        nr_noduri[node] = 0;
    }

    queue <int> q;
    q.push(source);
    dist[source] = 0;
    nr_noduri[source] = 1;
    in_queue[source] = true;

    while (!q.empty())
    {
        int node = q.front();
        q.pop();
        in_queue[node] = false;

        if (nr_noduri[node] > n)
        {
            fout << "Ciclu negativ!";
            cycle = true;
            return;
        }

        for (auto vecin : g[node])
        {
            if (dist[node] + vecin.second < dist[vecin.first])
            {
                dist[vecin.first] = dist[node] + vecin.second;
                nr_noduri[vecin.first] = nr_noduri[node] + 1;
                if (!in_queue[vecin.first])
                {
                    q.push(vecin.first);
                    in_queue[vecin.first] = true;
                }
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, cost;
        fin >> x >> y >> cost;
        g[x].push_back({y, cost});
    }

    bellman_ford(1);

    if (!cycle)
        for (int node = 2; node <= n; node++)
            fout << dist[node] << ' ';
    return 0;
}