#include <stdio.h>
#include <vector>
#include <set>
#include <cstring>
#define N_MAX 50003
#define M_MAX 250003
#define INFINIT 999999

using namespace std;

FILE *f, *g;

int n, m;
int d[N_MAX]; // vectorul ce contine costurile de la varful START pana la fiecare varf din graf
const int START = 1;

vector<int> v[N_MAX]; //un vector static ce contine vectori alocati dinamic, reprezinta lista de adiacenta
vector<int> cost[N_MAX]; // costurile drumuli dintre doua noduri, construita sub forma listelor de adiacenta
set< pair<int, int> > lista; // ca o coada, doar ca ordonata

inline void citire();
void Dijkstra(int);
inline void afisare();

int main()
{
    citire();
    Dijkstra(START);
    afisare();

    fclose(f);
    fclose(g);

    return 0;
}

inline void citire(){
    f = fopen("dijkstra.in", "r");
    g = fopen("dijkstra.out", "w");

    fscanf(f, "%d %d\n", &n, &m);

    int x, y;
    int c;

    for (int i = 1; i <= m; ++i){
        fscanf(f, "%d %d %d\n", &x, &y, &c);
        v[x].push_back(y);
        cost[x].push_back(c);
    }
}

void Dijkstra(int start){
    int nod;
    int c;
    int i;
    int v_size;

    lista.insert(make_pair(0, start));
    memset(d, INFINIT, sizeof(d)); // initializez vectorul de distante
    d[start] = 0;

    while (!lista.empty()){
        c = lista.begin()->first;
        nod = lista.begin()->second;
        lista.erase(lista.begin());
        v_size = v[nod].size();

        for (i = 0; i < v_size; ++i){
            if (d[v[nod][i]] > c + cost[nod][i]){ // daca drumul e mai avantajos cand trece prin nodul curent i, atunci reactualizam  vectorul d
                d[v[nod][i]] = c + cost[nod][i];
                lista.insert(make_pair(d[v[nod][i]], v[nod][i]));
            }
        }
    }
}

inline void afisare(){
    for (int i = 2; i <= n; ++i){
        if (d[i] < INFINIT)
            fprintf(g, "%d ", d[i]);
        else
            fprintf(g, "0 ");
    }
    fprintf(g, "\n");
}