#include <fstream>       // cout
#include <queue>          // queue
#include <vector>
#define NMAX 50002
#define INF 1000000000

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

int n,start=1;
struct varf{int x; int c;};
vector<varf>G[NMAX];
int cmin[NMAX]; //cmin[x]=costul drumului de cost minim de la start la x;
int nr[NMAX];   // nr[x]=de cate ori a fost actualizat un drum de cost minim de la start la x;
queue<int>C;

void citire();
bool bellman_ford();


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]<<' ';
fout.close();
return 0;
}

void citire()
{int i,j,c,m,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, si 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();
    //parcurd 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;
}