#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[10000],n,m,x,y,c,nod,itnod[10000];
bool ok[10000];
queue <int> Q;
vector< pair< int, int > > G[10000];
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();
        Q.pop();
        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;}
                }
                    }
            }
    }
    for(i=2;i<=n;i++)
        g<<D[i]<<' ';
    return 0;
}