//dijkstra rezolvare cu heap-uri

#include <cstdio>
#include <vector>
#include <iostream>

FILE *fin = fopen("dijkstra.in", "r");
FILE *fout = fopen("dijkstra.out", "w");

#define MAXN 50000
#define MAXM 250000
#define MAXC 5100000000
#define LL long long

int h[MAXN + 1], poz[MAXN + 1], k;
LL dist[MAXN + 1];

std::vector<std::pair<int, int>> v[MAXM + 1];
std::vector<std::pair<int, int>>::iterator it;

void swap(int a, int b) {
    int t = h[a];
    h[a] = h[b];
    h[b] = t;
}

void upheap(int x) {
    int t;
    while (x > 1) {
        t = x / 2;
        if(dist[h[t]] > dist[h[x]]) {
            poz[h[x]] = t;
            poz[h[t]] = x;

            swap(t, x);

            x = t;
        }
        else {
            return;
        }
    }
}

void downheap(int x) {
    int f;
    while(x <= k) {
        if (x * 2 <= k) {
            f = x * 2;
            if (f + 1 <= k)
                if (dist[h[f]] > dist[h[f + 1]])
                    f++;
            if (dist[h[x]] > dist[h[f]]) {
                poz[h[x]] = f;
                poz[h[f]] = x;

                swap(f, x);

                x = f;
            }
            else
                return;
        }
        else
            return;
    }
}

int main() {
    int n, m, x, y, c;
    //read
    fscanf(fin, "%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        fscanf(fin, "%d%d%d", &x, &y, &c);
        v[x].push_back(std::make_pair(y, c));
    }
    //marcam nodurile ca nevizitate
    for (int i = 2; i <= n; i++) {
        dist[i] = MAXC, poz[i] = -1;
    }
    //adaugam nodul de plecare in coada
    dist[1] = 0;
    h[1] = 1;
    poz[1] = 1;
    k++; //marimea cozii

    //cat timp exista elemente in coada
    while(k) {
        std::cout << "pas\n";
        //nodul cu valoarea minima este primul element din coada
        int min = h[1];
        std::cout << min << " ";
        //eliminam nodul curent din coada
        swap(1, k);
        poz[h[1]] = 1;
        k--;
        std::cout << k << "\n";
        downheap(1);
        std::cout << h[1] << " <--- ";
        //actualizarea distantelor vecinilor nodului curent
        for (it = v[min].begin(); it != v[min].end(); it++) {
            //nodul vecin
            y = it->first;
            //distanta de la nodul curent la nodul vecin
            c = it->second;
            //actualizam distanta minima de la nodul initial daca se poate obtine una mai buna
            if(dist[y] > dist[min] + c) {
                dist[y] = dist[min] + c;
                //daca nodul vecin era deja in coada, ii actualizam pozitia in coada
                if ( poz[y] != -1 )
                    upheap(poz[y]);
                //daca nodul vecin nu era in coada, il adaugam si actualizam coada
                else {
                    h[++k] = y;
                    poz[h[k]] = k;
                    upheap( k );
                    std::cout << k << " ";
                }
            }
        }
    }
    for (int i = 2; i <= n; i++)
        fprintf(fout, "%lld ", dist[i] == MAXC ? 0 : dist[i]);
    return 0;
}