#include <fstream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#define pb push_back
#define mp make_pair
#define inf 0x3f3f
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int D[250000],n,m,x,y,c,nod,itnod[250000];
bool ok[250000];
queue <int> Q;
vector< pair< int, int > > G[250000];
vector< pair< int, int > >::iterator it;
int main()
{
    int i;
    f>>n>>m;
    for (i=1;i<=m;i++) {
        f>>x>>y>>c;
        G[x].pb(mp(y,c));
    }
    memset(ok,false,sizeof(ok));
    memset (D,inf,sizeof(D));
    D[1]=0;
    memset(itnod,0,sizeof(itnod));
    Q.push(1);
    ok[1]=true;
    while(!Q.empty())
    {
        nod=Q.front();
        ok[nod]=false;
        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 (!ok[(*it).first])
                		{
                    			Q.push((*it).first);
                    			ok[(*it).first] = true;
                    			if (++itnod[(*it).first]>n)
                        			{g<<"Ciclu negativ!\n" ; return 0;}
                		}
                    }
		Q.pop();
   }
    for(i=2;i<=n;i++)
        g<<D[i]<<' ';
    return 0;
}