#include <iostream>
#include <vector>
#include <queue>
#include <climits>

#define ll long long 

using namespace std;

struct element
{
    bool seen = false;
    ll mini = LLONG_MAX;
    vector <pair<ll, ll> > sz;
};

struct edges
{
    ll where, sum;
};
priority_queue <edges> que;

bool operator < (const edges &a, const edges &b)
{
    return a.sum > b.sum;
}

edges act;
ll n, m, i;
int main()
{
    cin >> n >> m;
    vector <element> x(n + 1);
    ll a, b, c;
    for (i = 1; i <= m; ++i)
    {
        cin >> a >> b >> c;
        x[a].sz.push_back({ b,c });

    }

    que.push({ 1,0 });
    while (!que.empty())
    {
        act = que.top();
        while (!que.empty() && x[act.where].seen)
        {
            que.pop();
            if (!que.empty()) act = que.top();
        }
        
        if (que.empty()) break;
        que.pop();

        x[act.where].mini = act.sum;
        x[act.where].seen = true;

        for (auto& e : x[act.where].sz)
        {
            if (!x[e.first].seen && x[e.first].mini > (act.sum + e.second))
            {
                x[e.first].mini = act.sum + e.second;
                que.push({ e.first,x[e.first].mini });

            }
        }

    }
    for (i = 2; i <= n; ++i) cout << x[i].mini << " ";
}