#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];
struct Edge{
    int from, to, cost;
}U[M_MAX];

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

//Initializam lista dist[] cu infinit
void makeset(){
    for(int i = 1; i <= nrNod; i++)
        dist[i] = inf;
}

//Rezolvare
void Bellman_Ford(int start = 1){
    makeset();
    dist[start] = 0;

    bool relaxedEdge = true;

    for(int v = 1; v <= nrNod-1 && relaxedEdge; v++){
        relaxedEdge = false;
        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;
                relaxedEdge = true;
            }
    }
}

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

int main()
{
    citire();
    Bellman_Ford();
    afisare_dist();

    return 0;
}