#include <fstream>
#include <cstdlib>
#include <vector>
#include <cstring>

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

int c[50010];
int inStack[50010];
bool isInStack[50010];

int in,sf,n,m,i,x,y,nod,cost,b;

struct muchie
{
    int nod,cost;
} tmp;

int coada[500010];

vector<muchie> v[50010];

void bfs()
{
    in=1;
    sf=0;

    memset(c,0x3f,sizeof(c));

    coada[++sf]=1;

    inStack[1]=1;

    c[1]=0;
    isInStack[1]=1;

    while(in<=sf)
    {
        nod=coada[in];

        isInStack[nod]=0;


        for(i=0; i<v[nod].size(); i++)
        {


            tmp=v[nod][i];
            b=tmp.nod;
            if(!isInStack[b] && tmp.cost+c[nod]<c[b])
            {


                coada[++sf]=b;
                inStack[b]++;


                isInStack[b]=1;

                x=tmp.cost+c[nod];

                if(x<c[b])
                    c[b]=x;


                if(inStack[b]>=n)
                {
                    fout<<"Ciclu negativ!";
                    exit(0);
                }
            }

        }
        in++;
    }

    for(i=2; i<=n; i++)
        fout<<c[i]<<' ';


}


int main()
{

    fin>>n>>m;


    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>cost;

        tmp.nod=y;
        tmp.cost=cost;

        v[x].push_back(tmp);


    }


    bfs();

    return 0;
}