#include <iostream>
#include <fstream>
using namespace std;

ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");

#define N_MAX 50005
#define M_MAX 250005
#define inf 2000000000

//Declarare
int nrNod, nrMuchii, dist[N_MAX];
//int coada[M_MAX], first = 1, last = 1;
struct Edge{
    int from, to, cost;
}U[M_MAX];


void citire(){
    fin >> nrNod >> nrMuchii;
    for(int i = 1; i <= nrMuchii; i++)
        fin >> U[i].from >> U[i].to >> U[i].cost;
}

void makeset(){
    for(int i = 1; i <= nrNod; i++)
        dist[i] = inf;
}

void afisare_dist(){
    for (int i = 2; i <= nrNod; ++i) {
        if (dist[i] == inf) {
            dist[i] = 0;
        }
        fout << dist[i] << ' ';
    }
}

void Bellman_Ford(int start = 1){    // Argument default: 1
    makeset();
    dist[start] = 0;
    for(int k = 1; k <= nrNod-1; k++)
       for(int i = 1; i <= nrMuchii; i++)
        if( dist[U[i].from] + U[i].cost < dist[U[i].to] ) //Daca dist[from] + cost < dist[to]
            dist[U[i].to] = dist[U[i].from] + U[i].cost;

    for(int k = 1; k <= nrNod-1; k++)
        for(int i = 1; i <= nrMuchii; i++)
            if( dist[U[i].from] + U[i].cost < dist[U[i].to] )
                dist[U[i].to] = -inf;
}


int main()
{
    citire();
    Bellman_Ford();     // Drum minim de la 1 la celelalte noduri
    afisare_dist();
    return 0;
}