#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

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

int n, m, dp[50005];
vector <pair<int, int> > a[50005];
int cnt[50005];
queue <int> Q;
void Test_Case()
{
    int i, x, y, c, IsNegativeCycle;
    fin >> n >> m;
    while (m--)
    {
        fin >> x >> y >> c;
        a[x].push_back({ c, y });
    }

    for (i = 1; i <= n; i++)
        dp[i] = INF;

    dp[1] = 0;
    Q.push(1);
    cnt[1] = 1;
    IsNegativeCycle = 0;
    while (!Q.empty() and !IsNegativeCycle)
    {
        x = Q.front();
        Q.pop();
        for (auto w : a[x])
        {
            if (dp[w.second] > dp[x] + w.first)
            {
                dp[w.second] = dp[x] + w.first;
                if (cnt[w.second] > n)
                    IsNegativeCycle = 1;
                else
                {
                    Q.push(w.second);
                    cnt[w.second]++;
                }
            }
        }
    }

    if (IsNegativeCycle)
        fout << "Ciclu negativ!\n";
    else
        for (i = 2; i <= n; i++)
            fout << dp[i] << " ";

}

int main()
{
    int t;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    t = 1;
    while (t--)
        Test_Case();

    return 0;
}