#include <bits/stdc++.h>
#define N 50001
#define M 250001
#define inf 300000000
using namespace std;

FILE *f1 = fopen("bellmanford.in", "r");
FILE *f2 = fopen("bellmanford.out", "w");

int n, m, i, a, b, c, v[N], d[N];
long long val, steps;
vector<pair<int, int>>G[N];

struct ed{
    int x, y, c;
}edge[M];

class comp{
public:
    bool operator() (const pair<int, int>A, const pair<int, int> B)
    {
        return A.second > B.second;
    }
};

priority_queue<pair<int, int>, vector<pair<int ,int>>, comp> Q;

void bford()
{
    int i, node;
    pair<int ,int>x;
    for (i = 1; i <= n; i++)
        d[i] = inf;
    d[1] = 0;
    v[1] = 1;
    Q.push(make_pair(1, 0));
    steps = 0;
    val = (long long)(n-1) * (long long)m;
    while (!Q.empty() && steps < val)
    {
        x = Q.top();
        Q.pop();
        node = x.first;
        v[node] = 0;
        for (i = 0; i < G[node].size(); i++)
            if (d[G[node][i].first] > G[node][i].second + x.second)
            {
                d[G[node][i].first] = G[node][i].second + x.second;
                if (v[G[node][i].first] == 0)
                {
                    v[G[node][i].first] = 1;
                    Q.push(make_pair(G[node][i].first, d[G[node][i].first]));
                }
            }
        steps++;
    }
}

int main()
{
    fscanf(f1, "%d%d", &n, &m);
    for (i = 1; i <= m; i++)
    {
        fscanf(f1, "%d%d%d", &a, &b, &c);
        G[a].push_back(make_pair(b, c));
        edge[i].x = a;
        edge[i].y = b;
        edge[i].c = c;
    }
    bford();
    for (i = 1; i <= m; i++)
    {
        if (d[edge[i].y] > d[edge[i].x] + edge[i].c)
        {
            fprintf(f2, "Ciclu negativ!\n");
            fclose(f1);
            fclose(f2);
            return 0;
        }
    }
    for (i = 2; i <= n; i++)
        fprintf(f2, "%d ", d[i]);
    fclose(f1);
    fclose(f2);
    return 0;
}