#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <iomanip>

#define NMAX 50000

using namespace std;

ifstream F("dijkstra.in");
ofstream G("dijkstra.out");

const int INF = 0x3F3F3F3F;
vector<vector<pair<int, int>>> list(NMAX + 1);
vector<int> d(NMAX + 1), p(NMAX + 1);

int N, M;

void Read() {
    int x, y, w;

    F >> N >> M;

    for (int i = 0; i < M; i++) {
        F >> x >> y >> w;

        list[x].push_back(make_pair(y, w));
    }
}

void Dijkstra(int s) {
    int c, to, cost;
    d.assign(N + 1, INF);
    p.assign(N + 1, -1);

    set<pair<int, int>> st;
    st.insert({ d[s], s });

    d[s] = 0;

    while (!st.empty()) {
        c = st.begin()->second;
        st.erase(st.begin());

        for (pair<int, int> edge : list[c]) {
            to = edge.first;
            cost = edge.second;

            if (d[c] + cost < d[to]) {
                st.erase({ d[to], to });
                d[to] = d[c] + cost;
                p[to] = c;
                st.insert({ d[to], to });
            }
        }
    }
}

void Print() {
    for (int i = 2; i <= N; i++) {
        G << d[i] << " ";
    }
}

int main()
{
    Read();
    Dijkstra(1);
    Print();

    return 0;
}