#include <fstream>
#include <queue>
#include <vector>
#define NMAX 50003
#define INF 500000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct varf{int x,c;};
int cmin[NMAX];  ///cmin[x]=costul drumului minim de la start la x
int nr[NMAX];    ///de cate ori a fost acualizat drumul minim de la start la x
queue<int> C;
vector<varf> G[NMAX];
bool bellman_ford();
void citire();
int start=1,n,m;
int main ()
{int i;

    citire();
    if(!bellman_ford())
        fout<<"Ciclu negativ!";
        else
        for(i=2;i<=n;i++)
        if(cmin[i]==INF) fout<<INF<<' ';
        else
            fout<<cmin[i]<<' ';

    return 0;
}
void citire()
{
    int i,j,c,k; varf aux;
    fin>>n>>m;
    for(k=0;k<m;k++)
    {
        fin>>i>>j>>c;
        aux.x=j; aux.c=c;
        G[i].push_back(aux);
    }
}
bool bellman_ford()
///returnam 0 daca nu exista solutie
///returnam 1 daca exista solutie
{
    int i,vf;
    ///initializare
    for(i=1;i<=n;i++) cmin[i]=INF;
    cmin[start]=0;
    C.push(start);
    while(!C.empty())
    {
        vf=C.front();
        C.pop();
        ///parcurg lista de adiacenta a lui x
        for(i=0;i<G[vf].size();i++)
            if(cmin[G[vf][i].x]>cmin[vf]+G[vf][i].c)
                {
                 cmin[G[vf][i].x]=cmin[vf]+G[vf][i].c;
                 nr[G[vf][i].x]++;
                 if(nr[G[vf][i].x]==n) return 0;
                 C.push(G[vf][i].x);
                }
    }
    return 1;


}