#include <fstream>
#include <vector>
#define nmax 50005
#define mmax 250005
using namespace std;
fstream f1("bellmanford.in", ios::in);
fstream f2("bellmanford.out", ios::out);
int n, m,  viz[nmax], nrit[nmax], dist[nmax], prim, ultim, k, coada[mmax], ok=1;
vector <pair<int, int> > v[nmax];
void citire()
{
    int i, x, y, c;
    f1>>n>>m;
    for(i=1; i<=m; i++)
    {
        f1>>x>>y>>c;
        v[x].push_back({y, c});
    }
    for(i=2; i<=n; i++)
        dist[i]=2000000000;
    dist[1]=0;
    prim=ultim=k=1;
    coada[ultim]=1;
    viz[1]=1;
    nrit[1]=1;
}
void solutie()
{
    int nod, vec, ct;
    while(k!=0)
    {
        nod=coada[prim];
        prim++; k--; viz[nod]=0;
        if(prim> mmax-2) prim=1;
        for(auto it=v[nod].begin(); it!=v[nod].end(); ++it)
        {
            vec=(*it).first; ct=(*it).second;
            if(dist[vec]> dist[nod]+ct)
            {
                dist[vec]= dist[nod]+ct;
                if(!viz[vec])
                {
                    viz[vec]=1;ultim++; k++; coada[ultim]=vec;
                    if(ultim> mmax-2) ultim=1;
                    nrit[vec]++;
                    if(nrit[vec]> n) {ok=0;k=0; break;}
                }
            }
        }
    }
}
void afis()
{
    if(!ok) f2<<"Ciclu negativ!";
    else for(int i=2; i<=n; i++)
        f2<<dist[i]<<' ';
}
int main()
{
    citire();
    solutie();
    afis();
    return 0;
}