//Arbori de intervale
/*#include<iostream>
#include<fstream>
#define nmax 100001

int n,m,ans;
int Arb[4*nmax],x[nmax];

void ConstrArb(int nod,int st,int dr,int a,int b,int val)
{
    int mij=(st+dr)/2;
    if(a<=st && dr<=b)
    {
        if(st==dr)
            {Arb[nod]=val;
            return;
            }
        else //[st,dr] e inclus in a[b]
        Arb[nod]=std::max(Arb[2*nod],Arb[2*nod+1]);

    }
    else
    {
        if(a<=mij)
            ConstrArb(nod*2,st,mij,a,b,val);
        if(b>mij)
            ConstrArb(nod*2+1,mij+1,dr,a,b,val);
        Arb[nod]=std::max(Arb[2*nod],Arb[2*nod+1]);

    }


}

void query(int nod,int st,int dr,int a,int b)
{
    int mij=(st+dr)/2;
    if(a<=st && dr<=b)
    {
        ans=std::max(ans,Arb[nod]);

    }
    else
    {
        if(a<=mij)
            query(nod*2,st,mij,a,b);
        if(b>mij)
            query(nod*2+1,mij+1,dr,a,b);
        //ans=std::max(ans,std::max(Arb[2*nod],Arb[2*nod+1]));

    }


}


int main()
{
    int i,c,a,b;
    std::ifstream fin("arbint.in");
    std::ofstream fout("arbint.out");
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>x[i];
        ConstrArb(1,1,n,i,i,x[i]);
        //O(n log n)
    }
    for(i=1;i<=m;i++)
    {
        fin>>c;
            if(c)
            {
                fin>>a>>b;
                ConstrArb(1,1,n,a,a,b);

            }
            else
            {
                fin>>a>>b;
                ans=0;
                query(1,1,n,a,b);
                fout<<ans<<'\n';

            }
            //O(m log n)
    }

}*/
//range minimum query
/*#include<iostream>
#include<fstream>
#define nmax 100001
#define Inf nmax+7

int n,m,ans;
int Arb[4*nmax],x[nmax];

void ConstrArb(int nod,int st,int dr,int a,int b,int val)
{
    int mij=(st+dr)/2;
    if(a<=st && dr<=b)
    {
        if(st==dr)
            {Arb[nod]=val;
            return;
            }
        else //[st,dr] e inclus in a[b]
        Arb[nod]=std::min(Arb[2*nod],Arb[2*nod+1]);

    }
    else
    {
        if(a<=mij)
            ConstrArb(nod*2,st,mij,a,b,val);
        if(b>mij)
            ConstrArb(nod*2+1,mij+1,dr,a,b,val);
        Arb[nod]=std::min(Arb[2*nod],Arb[2*nod+1]);

    }


}

void query(int nod,int st,int dr,int a,int b)
{
    int mij=(st+dr)/2;
    if(a<=st && dr<=b)
    {
        ans=std::min(ans,Arb[nod]);

    }
    else
    {
        if(a<=mij)
            query(nod*2,st,mij,a,b);
        if(b>mij)
            query(nod*2+1,mij+1,dr,a,b);
        //ans=std::max(ans,std::max(Arb[2*nod],Arb[2*nod+1]));

    }


}


int main()
{
    int i,c,a,b;
    std::ifstream fin("rmq.in");
    std::ofstream fout("rmq.out");
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>x[i];
        ConstrArb(1,1,n,i,i,x[i]);
        //O(n log n)
    }
    for(i=1;i<=m;i++)
    {
                fin>>a>>b;
                ans=Inf;
                query(1,1,n,a,b);
                fout<<ans<<'\n';

    }
            //O(m log n)
}*/

//Bellman-Ford (optimizare cu o coada)
#include<bits/stdc++.h>
#define nmax 50005
#define Inf 1001
using namespace std;

vector < pair<int,int> > G[nmax];
int n,m,neg;

queue <int> Q;
int viz[nmax],d[nmax];


void read()
{
    int x,y,z;
    ifstream fin("bellmanford.in");
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>z;
        G[x].push_back(make_pair(y,z));
    }
    fin.close();
}


void bellman_ford(int start)
{
    int nod,i,nropt[nmax]={0};
    for(i=1;i<=n;i++)
        d[i]=Inf*nmax;
    d[start]=0;
    Q.push(start);
    viz[start]=1;
    while(!Q.empty() && !neg)
    {
        nod=Q.front();
        Q.pop();
        viz[nod]=0;

        vector< pair < int,int > >::iterator it;
        for(it=G[nod].begin();it!=G[nod].end();it++)
            if(d[it->first]>d[nod]+it->second)
            {
                d[it->first]=d[nod]+it->second;
                if(!viz[it->first])
                {
                    if(nropt[it->first]==n) neg=1;
                    Q.push(it->first);
                    viz[it->first]=1;
                    nropt[it->first]++;
                }

            }

    }


}

int main()
{
    read();
    bellman_ford(1);
    ofstream fout("bellmanford.out");
    if(!neg)
    for(int i=2;i<=n;i++)
        fout<<d[i]<<' ';
    else
        fout<<"Ciclu negativ!";
}