#include <bits/stdc++.h>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int N = 5e4 + 1, INF32 = 0x3f3f3f3f;
int n, m, x, y, w, poz[N], d[N], h, heap[2 * N];
vector<pair<int, int>> c[N];

void coboara(int p){
    int bun = p;
    if(2 * p <= h && d[heap[2 * p]] < d[heap[bun]])
        bun = 2 * p;

    if(2 * p + 1 <= h && d[heap[2 * p + 1]] < d[heap[bun]])
        bun = 2 * p + 1;

    if(bun != p){
        swap(poz[heap[p]], poz[heap[bun]]);
        swap(heap[p], heap[bun]);
        coboara(bun);
    }
}

void urca(int p){
    while(p > 1 && d[heap[p]] < d[heap[p / 2]]){
        swap(poz[heap[p]], poz[heap[p / 2]]);
        swap(heap[p], heap[p / 2]);
        p /= 2;
    }
}

void sterge(int p){
    poz[heap[p]] = 0;
    if(p == h){
        h--;
        return;
    }

    heap[p] = heap[h--];
    coboara(p);
}

void scrieHeap(){
    static int count;
    cout << "[COUNT]  " << ++count << '\n';
    cout << "[ELEMENTS]  " << h << '\n';
    cout << "--------\n";
    cout << "[DISTANCE]\n";
    for(int i = 1; i <= n; i++)
        cout << i << " : " << d[i] << ' ' << poz[i] << '\n';

    cout << "--------\n";
    cout << "[HEAP]\n";
    for(int i = 1; i <= h; i++)
        cout << i << " : " << heap[i] << ' ' << d[heap[i]] << ' ' << poz[heap[i]] << '\n';

    cout << "\n\n";
}

void dijkstra(int start){
    for(int i = 1; i <= n; i++)
        d[i] = INF32;

    d[start] = 0;
    heap[++h] = start;
    poz[h] = start;
    while(h > 0){
        int x = heap[1];
        sterge(1);
        for(auto e: c[x]){
            int y = e.first, w = e.second;
            if(d[x] + w < d[y]){
                //cout << "FOUND IMPROVEMENT: SRC DEST NEWLEN\n";
                //cout << x << ' ' << y << ' ' << d[x] + w << '\n';
                d[y] = d[x] + w;
                if(poz[y] == 0){
                    heap[++h] = y;
                    poz[y] = h;
                }

                urca(poz[y]);
                //scrieHeap();
            }
        }
    }
}

int main(){
    f >> n >> m;
    for(int i = 0; i < m; i++){
        f >> x >> y >> w;
        c[x].push_back({y, w});
    }

    f.close();
    dijkstra(1);
    for(int i = 2; i <= n; i++)
        g << (d[i] == INF32 ? 0 : d[i]) << ' ';

    g.close();
}