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

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

const int NMAX=50050, inf=1000000000;

int n,m;
vector<pair<int,int> >lista[NMAX];
int d[NMAX];
queue<int>q;
bool ciclu;
int nrAparitii[NMAX];
void citire()
{
    fin>>n>>m;
    int a,b,c;
    for (int i=1; i<=m; i++){
        fin>>a>>b>>c;
        lista[a].push_back(pair<int,int>(b,c));
    }
}
void bellmanford()
{
    for (int i=1; i<=n; i++)
        d[i]=inf;
    d[1]=0;
    q.push(1);
    nrAparitii[1]=1;
    int cont;
    while (!q.empty() && !ciclu){
        cont=q.front();
        q.pop();
        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;
                nrAparitii[it->first]++;
                if (nrAparitii[it->first]>n){
                    ciclu=true;
                }
                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();
    bellmanford();
    afisare();
    return 0;
}