#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <vector>
#include <set>

#define maxN 50005
#define maxM 250005
#define INF 90000000
using namespace std;

typedef pair<int, int> nodAndCost;

int N, M, c, x, y;
vector<nodAndCost > arr[maxN];
vector<int> cost(maxN, INF);
set < nodAndCost > S;

void citireMuchii() {
    for(int i = 1; i <= M; ++i) {
        scanf("%d %d %d", &x, &y, &c);
        arr[x].push_back(make_pair(y, c));
    }
}
void afisareMuchii() {
    for(int i = 1; i <= N; ++i) {
        printf("%d: ", i);
        for(int j = 0; (unsigned)j < arr[i].size(); ++j) {
            printf(" %d, c = %d ", arr[i][j].first, arr[i][j].second);
        }
        printf("\n");
    }
}

void dijkstra_heap(int start) {
    int pminNode, pminCost, calcActual, currNeighbour, currNeighbourC;
    cost[start] = 0;
    S.insert(make_pair(start, cost[start]));
    while(S.size() > 0) { // cautarile de minim pentru n noduri
        // acum extrag minimul din set
        pminNode = (*S.begin()).first;
        pminCost = (*S.begin()).second;

        S.erase(S.begin());

        // pentru toti vecinii ii iau si ii inserez cu valoarea mai mica daca e posibil in set
        for(int k = 0; (unsigned)k < arr[pminNode].size(); ++k) {
            currNeighbour = arr[pminNode][k].first;
            currNeighbourC = arr[pminNode][k].second;
            calcActual = currNeighbourC + pminCost;
            if (cost[currNeighbour] > calcActual) {
                cost[currNeighbour] = calcActual;
                S.insert(make_pair(currNeighbour, cost[currNeighbour]));
            }
        }
    }
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d %d", &N, &M);
    citireMuchii();
    dijkstra_heap(1);
    for(int i = 2; i <= N; ++i)
            printf("%d ", (cost[i] == INF) ? 0: cost[i]);
    return 0;
}