#include <bits/stdc++.h>

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
const int nmax = 50005;
const int inf = 2000000;
int N,M,cnt[nmax],dp[nmax];
bool CN;
bool viz[nmax];


struct el
{
    int x,cost;
};
queue < el > Q;
vector < el > L[nmax];

inline void Read()
{
    fin >> N >> M;
    int i,x;
    el w;
    for(i = 1; i <= M; i++)
    {
        fin >> x >> w.x >> w.cost;
        L[x].push_back(w);
    }
}


inline void BLMFRD()
{
    int i;
    el w,w2;
    w.x = 1; w.cost = 0;
    Q.push(w);
    for(i = 2; i <= N; i++) dp[i] = inf;
    while(!Q.empty() && !CN)
    {
        w = Q.front();
        Q.pop();
        if(cnt[w.x] > N) CN = true;
        viz[w.x] = false;
        for(auto it : L[w.x])
        {
            if(dp[it.x] > dp[w.x] + it.cost)
            {
                cnt[it.x]++;
                dp[it.x] = dp[w.x] + it.cost;
                if(!viz[it.x])
                {
                    viz[it.x] = true;
                    w2.x = it.x; w2.cost = dp[it.x];
                    Q.push(w2);
                }
            }
        }
    }
}


inline void Print()
{
    if(CN) fout << "Ciclu negativ!\n";
    else
    {
        for(int i = 2; i <= N; i++) fout << dp[i] << " ";
        fout << "\n";
    }
    fout.close();
}

int main()
{
    Read();
    BLMFRD();
    Print();
    return 0;
}