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

struct nod {
    int i;
    int cost;
};

void dijkstra(vector<vector<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;
        vector<nod> muchii(adc[nodCurent]);
        // parcurge-i muchiile si vezi distantele
        for (int j = 0; j < muchii.size(); j++) {
            nod muchie = muchii[j];
            if (muchie.cost + dist[nodCurent] < dist[muchie.i])
                dist[muchie.i] = dist[nodCurent] + muchie.cost;
        }
        // vizitat
        vizitat[nodCurent] = true;
    }
}

int main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    vector<vector<nod> > adc(NOD_MAX);
    // citire noduri
    int n, m;
    cin >> n >> m;
    int a, b, c;
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        nod nou;
        nou.i = b; nou.cost = c;
        adc[a].push_back(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] << ' ';
    }
}