#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 50005, inf = 2000000000;

bool viz[NMAX], ciclu;
int n,m;
int dp[NMAX],cnt[NMAX];

struct el
{
    int nod,cost;
};

vector < el > L[NMAX];
queue <int> Q;

inline void read()
{
    int x;
    el k;
    fin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> k.nod >> k.cost;
        L[x].push_back(k);
    }
}

inline void Bellman_Ford()
{
    int nod, newnod, cost;
    for(int i = 2; i <= n; i++)
        dp[i] = inf;
    viz[1] = true;
    cnt[1] = 1;
    Q.push(1);
    while(!Q.empty () && !ciclu)
    {
        nod = Q.front();
        viz[nod] = false;
        Q.pop();
        for(auto it : L[nod])
        {
            newnod = it.nod;
            cost = it.cost;
            if(dp[newnod] > dp[nod]+cost)
            {
                dp[newnod] = dp[nod]+cost;
                if(!viz[newnod])
                {
                    viz[newnod] = true;
                    cnt[newnod]++;
                    if(cnt[newnod] > n)
                        ciclu = true;
                    Q.push(newnod);
                }
            }
        }
    }
    if(ciclu)
        fout<<"Ciclu negativ!";
    else
        for(int i = 2; i <= n; i++)
            fout << dp[i] << " ";
    fout<<"\n";
}


int main()
{
    read();
    Bellman_Ford();
    return 0;
}