#include <fstream>
#include <vector>
#include <queue>
# define NMAX 50002
#define INF 1000000000
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");

struct varf {int x; int c; };
vector<varf> G[NMAX];
int n, m, start=1;
int cmin[NMAX];  /// costul minim de la start la i
int nr[NMAX]; /// de cate ori a fost actualizat drumul de la start la x
queue <int> C;
void citire();
bool b_ford();

int main()
{ int i;
    citire();
    if (!b_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()
{ varf aux;
    int i, j, c;
    fin>>n>>m;
    while(fin>>i>>j>>c)
    {
        aux.x=j; aux.c=c;
        G[i].push_back(aux);

    }
}
bool b_ford() /// returnam 0 daca nu exista solutie si 1 daca exista
{/// initializare
    int i, vf;
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;
}