#include <fstream>
#include <queue>
#include <vector>
#define NMAX 50002
#define INF 100000000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n,start;
int cmin[NMAX];///cmin[x]=costul drmului de cost minim de la start la x
int nr[NMAX];///nr[x]=de cate ori a fost actualizat costul drumului
queue<int> C;

struct varf{int x;int c;};
vector<varf> G[NMAX];

void citire();
bool bellman_ford();
void afisare();
int main ()
{   int i;
  citire();
  if(!bellman_ford())
    fout<<"Ciclu negativ!";
    else
        for(i=2;i<=n;i++)
        if(cmin[i]==INF) fout<<-1<<' ';
            else fout<<cmin[i]<<' ';


  return 0;
}
void citire()
{   int k;
    varf aux;
    int i,j,c,m;
    fin>>n>>m;
    for(k=0;k<m;k++)
    {
        fin>>i>>j>>c;
        aux.x=j; aux.c=c;
        ///j intra in lista de adiacenta a lui i
        G[i].push_back(aux);
    }
}
bool bellman_ford()
///returnam 0 daca nu exista solutie
///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 vf
           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;
}