#include <iostream>
#include <cstring>
#include <fstream>
#include <vector>

using namespace std;
ifstream fin("test.in");
ofstream fout("test.out");
#define infi (1<<30)
#define f first
#define s second
vector <pair<int, int>> heap;
vector <pair<int, int>> v[50002];
int n, m, i, x, y, dp[50002], le, z;

void down_heap() {
    int k = 0;
    heap[0] = heap[le - 1];
    while (2 * k + 1 <= le - 1) {
        if ((2 * k + 2 <= le - 1 && min(min(heap[k].s, heap[2 * k + 1].s), heap[2 * k + 2].s) == heap[k].s) || (2 * k + 1 == le - 1 && min(heap[k].s, heap[2 * k + 1].s) == heap[k].s))
            break;
        else if ((2 * k + 2 <= le - 1 && min(min(heap[k].s, heap[2 * k + 1].s), heap[2 * k + 2].s) == heap[2 * k + 1].s) || (2 * k + 1 == le - 1 && min(heap[k].s, heap[2 * k + 1].s) == heap[2 * k + 1].s)) {
            swap(heap[k], heap[2 * k + 1]);
            k = 2*k + 1;
        }
        else {
            swap(heap[k], heap[2 * k + 2]);
            k = 2*k + 2;
        }
    }
    heap.pop_back();
    le--;
}

void up_heap() {
    le++;
    int k = le - 1;
    while (k > 0 && heap[k].s < heap[int(k / 2)].s) {
        swap(heap[k], heap[int(k / 2)]);
        k = int(k / 2);
    }
}

void DIJ(){
    int nc, cc;
    heap.push_back(make_pair(1,0));
    le = 1;
    while(le != 0){
        nc = heap[0].f;
        cc = heap[0].s;
        down_heap();
        if (cc < dp[nc])
        {
            dp[nc] = cc;
            for (auto x : v[nc]) {
                if (dp[nc] + x.s < dp[x.f]) {
                    heap.push_back(make_pair(x.f, dp[nc] + x.s));
                    up_heap();
                }
            }
        }
    }
}

int main()
{
    fin>>n>>m;
    for(i = 1; i <= m; i++){
        fin>>x>>y>>z;
        v[x].push_back(make_pair(y, z));
    }
    for (i = 1; i <= n; i++)
        dp[i] = infi;
    DIJ();
    for(i = 2; i <= n; i++)
        fout<<dp[i]<<' ';
    return 0;
}