#include <vector>
#include <set>
#include <climits>
#include <fstream>
#define NOD_MAX 50001
const long long INF = 1000000005;
using namespace std;
// pbinfo #588 dijkstra
// adaptata pentru infoarena

struct nod {
    int i;
    int cost;
    nod* urm;
};

void dijkstra(nod* adc[], int n, int nodStart, long long dist[]) {
    bool vizitat[NOD_MAX];
    // initializeaza sirurile
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        vizitat[i] = false;
    }
    dist[nodStart] = 0;
    // pentru fiecare nod
    for (int i = 0; i < n; i++) {
        // cauta nodul cu dist cel mai mic, nevizitat
        int nodCurent = -1;
        long long dmin = INF;
        for (int j = 1; j <= n; j++) {
            if (dist[j] < dmin && !vizitat[j]) {
                nodCurent = j; dmin = dist[j];
            }
        }
        if (nodCurent == -1) break;
        nod* c = adc[nodCurent];
        // parcurge-i muchiile si vezi distantele
        while (c != NULL) {
            if (c->cost + dist[nodCurent] < dist[c->i])
                dist[c->i] = dist[nodCurent] + c->cost;
            c = c->urm;
        }
        // vizitat
        vizitat[nodCurent] = true;
    }
}

int main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    // citire noduri
    int n, m;
    cin >> n >> m;
    nod* adc[n+1];
    nod* adc_lastpos[n+1];
    for (int i = 1; i <= n; i++) {
        adc[i] = NULL;
        adc_lastpos[n] = NULL;
    }
    int a, b, c;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        nod* nou = new nod;
        nou->i = b; nou->cost = c;
        nou->urm = NULL;
        if (adc[a] == NULL) {
            adc[a] = nou;
            adc_lastpos[a] = nou;
        } else {
            adc_lastpos[a]->urm = nou;
            adc_lastpos[a] = nou;
        }
    }
    long long dist[NOD_MAX];
    dijkstra(adc, n, 1, dist);
    for (int i = 2; i <= n; i++) {
        if (dist[i] >= INF)
            cout << 0 << ' ';
        else cout << dist[i] << ' ';
    }
}