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

int m, n, start = 1;
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 costul drumului de cost minim de la start la x
struct varf {int x, c;};
vector<varf> G[NMAX];
queue<int> C;

void read();
bool bellmanford();
void print();

int main(){
    read();
    if(!bellmanford()) fout << "Ciclu negativ!\n";
    else print();
    fout.close();
    return 0;
}

void read(){
    int c, i, j, 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);
    }
}
/// 0 nu exista sol, 1 altfel
bool bellmanford(){
    int i, vf;

    /// initializarea
    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;
}

void print(){int i;
    for(i = 2; i <= n; i++)
        if(cmin[i] == INF) fout << -1 << ' ';
        else fout << cmin[i] << ' ';
    fout << '\n';
}