#include <bits/stdc++.h>
#define Nmax 50006
#define INF 1000000000
using namespace std;
ifstream f("bellmanford.in"); ofstream g("bellmanford.out");
int D[Nmax], use[Nmax];
struct vecin {int varf, cost;};
vector <vecin> L[Nmax];
queue <int> Q;
int main()
{   int n, m; f>>n>>m;
    for(int x, y, c; m; --m) {f>>x>>y>>c; L[x].push_back((vecin){y, c});}
    for(int i=1; i<=n; ++i) D[i]=INF;
    Q.push(1); D[1]=0;
    while(!Q.empty())
    {   int x=Q.front(); Q.pop(); use[x]++;
        if(use[x]==n) {g<<"Ciclu negativ!\n"; g.close(); f.close(); return 0;}
        vector <vecin> :: iterator it=L[x].begin(), sf=L[x].end();
        for(; it!=sf; ++it)
            if(D[(*it).varf]>D[x]+(*it).cost)
            {   D[(*it).varf]=D[x]+(*it).cost;
                Q.push((*it).varf);
            }
    }
    for(int i=2; i<=n; ++i) g<<D[i]<<' ';
    g<<'\n'; f.close(); g.close(); return 0;
}