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

using namespace std;

#define NMax 50001
#define Inf (1<<30)

int n, m, x, y, z;
vector<pair<int, int> > v[NMax];
int cost[NMax];

int bellman (int now) {
    queue<int> q;
    for (int i = 1; i <= n; i++)
        cost[i] = Inf;
    cost[now] = 0;

    vector<bool> inQ(n+1, 0);
    vector<int> cntInQ(n+1, 0);

    q.push (now);
    inQ[now] = true;
    while (!q.empty ()) {
        now = q.front ();
        q.pop ();
        inQ[now] = false;

        for (int i = 0; i < v[now].size (); i++)
            if (!inQ[v[now][i].first])
                if (cost[v[now][i].first] > cost[now] + v[now][i].second) {
                    cost[v[now][i].first] = cost[now] + v[now][i].second;
                    if (cntInQ[v[now][i].first] > n)
                        return 0;
                    else {
                        q.push (v[now][i].first);
                        inQ[v[now][i].first] = true;
                        cntInQ[v[now][i].first]++;
                    }
                }
    }
}

int main()
{
    ifstream fin ("bellmanford.in");
    ofstream fout ("bellmanford.out");

    fin >> n >> m;
    for (int i = 1; i <= m; i++)
        fin >> x >> y >> z,
        v[x].push_back (make_pair (y, z));
    if (!bellman(1))
        fout << "Ciclu negativ!\n";
    else
        for (int i = 2; i <= n; i++)
            fout << cost[i] << ' ';
    return 0;
}