#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

const int NMAX=50010,inf=1000000000;
int n,m;
int d[NMAX];
queue<int>q;
vector<pair<int,int> >lista[NMAX];
bool apare[NMAX],ciclu;
int nrAparitii[NMAX];
void citire()
{
    fin>>n>>m;
    pair<int,int> cont;
    int a;
    for (int i=1; i<=n; i++){
        d[i]=inf;
        apare[i]=true;
        q.push(i);
    }
    for (int i=1; i<=m; i++){
        fin>>a>>cont.first>>cont.second;
        lista[a].push_back(cont);
    }
}
void rezolvare()
{
    int cont;
    d[1]=0;
    while (!q.empty() && !ciclu){
        cont=q.front();
        q.pop();
        apare[cont]=false;
        for (vector<pair<int,int> >::iterator it=lista[cont].begin(); it!=lista[cont].end(); it++){
            if (d[it->first]>d[cont]+it->second){
                d[it->first]=d[cont]+it->second;
                if (!apare[it->first]){
                    if (nrAparitii[it->first]>n){
                        ciclu=true;
                    }else{
                        apare[it->first]=true;
                        nrAparitii[it->first]++;
                        q.push(it->first);
                    }
                }
            }
        }
    }
}
void afisare()
{
    if (ciclu){
        fout<<"Ciclu negativ!\n";
    }else{
        for (int i=2; i<=n; i++)
            fout<<d[i]<<' ';
        fout<<'\n';
    }
}
int main()
{
    citire();
    rezolvare();
    afisare();
    return 0;
}