#include<fstream>
#include<cstring>
#define inf 1<<30
#define nmax 50001
using namespace std;

struct nod_lista{
    int val,cost;
    nod_lista *link;
};

nod_lista *G[nmax],*Last[nmax];
int dist[nmax],nrc[nmax],Q[nmax],viz[nmax],S,N,M,ok;


void adauga(int unde,int ce,int cat)
{
    nod_lista *q=new nod_lista;
    q->val=ce;
    q->cost=cat;
    q->link=NULL;

    if(!G[unde])
    G[unde]=Last[unde]=q;
    else
    {
        Last[unde]->link=q;
        Last[unde]=q;
    }
}

void citeste()
{
    ifstream f("bellmanford.in");
    int i,x,y,c;

    f>>N>>M;
    for(i=1;i<=M;i++)
    {
        f>>x>>y>>c;
        adauga(x,y,c);
    }
    S=1;
}

void BellmanFord(int S)
{
    int p,q,nod,cost,vecin;
    nod_lista *it;

    viz[S]=1;
    ok=1;
    for(int i=1;i<=N;i++)
    dist[i]=inf;
    dist[S]=0;

    p=q=0;
    Q[++q]=S;
    while(p<q && ok)
    {
        nod=Q[++p];
        it=G[nod];
        while(it)
        {
            vecin=it->val;
            cost=it->cost;
            if(dist[vecin]>dist[nod]+cost)
            {
                dist[vecin]=dist[nod]+cost;

                Q[++q]=vecin;
                ++nrc[vecin];
                if(nrc[vecin]==N-1)
                ok=0;

            }

            it=it->link;
        }
    }
}

void rezolva()
{
    BellmanFord(S);
}

void scrie()
{
    ofstream g("bellmanford.out");
    int i;

    if(!ok)
    g<<"Ciclu de cost negativ!\n";
    else
    for(i=2;i<=N;i++)
    g<<dist[i]<<' ';

    g<<'\n';
    g.close();
}

int main()
{
    citeste();
    rezolva();
    scrie();
    return 0;
}