#include <bits/stdc++.h>
using namespace std;
string np = "bellmanford";
ifstream f(np + ".in");
ofstream g(np + ".out");

// #define f cin
// #define g cout

int n, m;
vector<int> d, k;
vector<pair<int, int>> adj[50003];

void djikstra(int nod)
{
    priority_queue<pair<int, int>> q;
    d.assign(n + 1, INT_MAX);
    k.resize(n + 1);
    d[nod] = 0;
    q.push({0, nod});
    while (!q.empty())
    {
        int curr = q.top().second;
        k[curr]++;
        if (k[curr] == n)
            g << "Ciclu negativ!", exit(0);
        if (-q.top().first > d[curr])
        {
            q.pop();
            continue;
        }
        q.pop();
        for (auto next : adj[curr])
            if (d[next.first] > d[curr] + next.second)
                d[next.first] = d[curr] + next.second,
                q.push({-d[next.first], next.first});
    }
}
int main()
{
    f >> n >> m;
    for (int i = 1, a, b, c; i <= m; i++)
        f >> a >> b >> c, adj[a].push_back({b, c});

    djikstra(1);

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

    return 0;
}