#include <bits/stdc++.h>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int nmax = 50005, inf = 2000000000;
bool viz[nmax],CicluNeg;
int n,m;
int dp[nmax],cnt[nmax];
struct el
{
    int nod,cost;
};
vector < el > L[nmax];
queue <int> Q;

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

inline void BellmanFord()
{
    int i,j,nod,Nnod,cost;
    for(i = 2; i <= n; i++) dp[i] = inf;
    viz[1] = true, cnt[1] = 1;
    Q.push(1);
    while(!Q.empty () && !CicluNeg)
    {
        nod = Q.front();
        viz[nod] = false;
        Q.pop();
        for(i = 0; i < L[nod].size(); i++)
        {
            Nnod = L[nod][i].nod;
            cost = L[nod][i].cost;
            if(dp[Nnod] > dp[nod]+cost)
            {
                dp[Nnod] = dp[nod]+cost;
                if(!viz[Nnod])
                {
                    viz[Nnod] = true;
                    cnt[Nnod]++;
                    if(cnt[Nnod] > n) CicluNeg = true;
                    Q.push(Nnod);
                }
            }
        }
    }
    if(CicluNeg) fout<<"Ciclu negativ!";
    else for(i = 2; i <= n; i++) fout<<dp[i] << " ";
    fout<<"\n";
    fout.close();
}


int main()
{
    Read();
    BellmanFord();
    return 0;
}