#include <fstream>
#include <vector>
#include <queue>
#define Nmax 50005

using namespace std;

int N,d[Nmax],cnt[Nmax];
bool viz[Nmax],CicluNeg;
queue <int> Q;

struct Muchie
{
    int nod,cost;
};
vector <Muchie> L[Nmax];

inline void Read()
{
    Muchie w;
    int i,x,M;
    ifstream fin("bellmanford.in");
    fin>>N>>M;
    for(i=1;i<=M;++i)
    {
        fin>>x>>w.nod>>w.cost;
        L[x].push_back(w);
    }
    fin.close();
}

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

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