#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
#include <vector>

using namespace std;

const int MAX = 50050;
const int INF = 0x3f3f3f3f;

#define c first
#define n second

int N, M;
int D[MAX];

vector< pair<int, int> > G[MAX];
priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > H;

void OpenFiles() {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
}

void CloseFiles() {
    fclose(stdin);
    fclose(stdout);
}

void Citire() {
    cin >> N >> M;
    for(int i = 1, A, B, C; i <= M; i++) {
        cin >> A >> B >> C;
        G[A].push_back( make_pair(C, B) );
    }
}

void Dijkstra() {
    memset(D, INF, sizeof(D));
    D[1] = 0;
    H.push(make_pair(0, 1));
    while(!H.empty()) {
        int nod = H.top().n;
        H.pop();
        for(size_t i = 0; i < G[nod].size(); i++) {
            int dest = G[nod][i].n, C = G[nod][i].c;
            if(D[dest] > D[nod] + C) {
                D[dest] = D[nod] + C;
                H.push(make_pair(D[dest], dest));
            }
        }
    }
}

void Afisare() {
    for(int i = 2; i <= N; i++) 
        cout << D[i] << " ";
}

int main() {
    OpenFiles();
    Citire();
    Dijkstra();
    Afisare();
    CloseFiles();
}