#include <bits/stdc++.h>
#define MAX 50000 + 5
#define INF 1LL * 2e12

using namespace std;

typedef long long LL;
typedef pair<LL, LL> pairLL;

vector<pairLL>graph[MAX];
LL dist[MAX], vf[MAX];
int main()
{
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");

    ios::sync_with_stdio(false);
    fin.tie(0);
    fout.tie(0);
    srand(time(NULL));

    int n, m;

    fin >> n >> m;

    for(int i = 1; i <= m; i++)
    {
        int a, b, cost;

        fin >> a >> b >> cost;

        graph[a].push_back({b, cost});
    }

    queue<pairLL>Q;
    bool eCiclu = false;

    dist[1] = 0;
    for(int i = 2; i <= n; i++)dist[i] = INF;

    Q.push({1, 0});

    while(!eCiclu && Q.size())
    {
        int nod = Q.front().first;
        LL distCurrent = Q.front().second;

        Q.pop();

        for(auto vecin : graph[nod])
        {
            if(dist[vecin.first] > distCurrent + vecin.second)
            {
                dist[vecin.first] = distCurrent + vecin.second;
                vf[vecin.first]++;
                Q.push({vecin.first, dist[vecin.first]});

                if(vf[vecin.first] == n)
                    eCiclu = true;
            }
        }
    }

    if(eCiclu)fout << "Ciclu negativ!";
    else
        for(int i = 2; i <= n; i++)fout << dist[i] << " ";

    fin.close();
    fout.close();

    return 0;
}