#include <fstream>
#include <vector>
#include <queue>

using namespace std;
using edge = pair<int, int>;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

static constexpr int NMAX = (int)(5e4 + 1);
static const int INF = (int)(1e9);

int N, M;
vector<edge> G[NMAX];

auto cmp = [](const edge &a, const edge &b)
{
    if (!(a.first < b.first))
        return 1;

    return 0;
};
priority_queue<edge, vector<edge>, decltype(cmp)> H(cmp);

static inline void read()
{
    f.tie(nullptr);

    f >> N >> M;

    for (int i = 1; i <= M; ++i)
    {
        int a = 0, b = 0;
        f >> a >> b;

        int c = 0;
        f >> c;

        G[a].push_back({c, b});
    }

    return;
}

static inline vector<int> Dijkstra(const int &Source)
{
    vector<int> ans = {};
    vector<bool> Sel = {};
    for (int i = 0; i <= N; ++i)
        ans.push_back(INF), Sel.push_back(0);

    ans[Source] = 0, Sel[Source] = 1;
    for (auto &it : G[Source])
        if (it.first < ans[it.second])
            ans[it.second] = it.first, H.push(it);

    while (!H.empty())
    {
        while (!H.empty() && Sel[H.top().second])
            H.pop();

        if (H.empty())
            break;

        int node = H.top().second;
        int dist = H.top().first;

        Sel[node] = 1;
        H.pop();

        for (auto &it : G[node])
            if (!Sel[it.second] && (dist + it.first) < ans[it.second])
            {
                ans[it.second] = dist + it.first;

                H.push({ans[it.second], it.second});
            }
    }

    for (auto &it : ans)
        if (it == INF)
            it = 0;

    return ans;
}

int main()
{
    read();

    vector<int> dist = Dijkstra(1);

    for (int i = 2; i <= N; ++i)
    {
        g << dist[i];

        if (i < N)
            g << ' ';
        else
            g << '\n';
    }

    return 0;
}