#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define MAX_N 50015
#define PB push_back
#define MP make_pair
#define SZ(A) (int)((A).size())

typedef pair<int, int> PII;

int N, M;
vector<PII> lv[MAX_N];
priority_queue<PII, vector<PII>, greater<PII> > H;
bool viz[MAX_N];
int D[MAX_N];

void read() {
    scanf("%d %d", &N, &M);
    for (int i = 1; i <= M; ++i) {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        lv[a].PB(MP(b, c));
    }
}

void solve() {
    memset(D, 0x3f, sizeof(D));
    D[1] = 0;
    H.push(MP(0, 1));

    while (!H.empty()) {
        while (!H.empty() && viz[H.top().second])
            H.pop();
        if (H.empty()) break;

        int nod = H.top().second;
        viz[nod] = true;
        H.pop();

        for (int j = 0; j < SZ(lv[nod]); ++j)
            if (D[nod] + lv[nod][j].second < D[lv[nod][j].first]) {
                D[lv[nod][j].first] = D[nod] + lv[nod][j].second;
                H.push(MP(D[lv[nod][j].first], lv[nod][j].first));
            }
    }

    for (int i = 2; i <= N; ++i)
        printf("%d ", D[i]);
    printf("\n");
}

int main() {
    freopen(FIN, "r", stdin);
    freopen(FOUT, "w", stdout);
    read();
    solve();
    return 0;
}