#include<bits/stdc++.h>

using namespace std;

const int NMAX = 5e4 + 5, MMAX = 2e5 + 5e4 + 5;

int n, m, dist[NMAX];
bool viz[NMAX];
vector<pair<int, int>> v[NMAX];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

void bfs()
{
    q.push({0, 1});

    while(!q.empty())
    {
        int nodval = q.top().second, nodcost = q.top().first;
        q.pop();

        if(!viz[nodval])
        {
            viz[nodval] = true;
            dist[nodval] = nodcost;
            
            for(auto nod : v[nodval])
            {
                if(!viz[nod.first])
                    q.push({nodcost + nod.second, nod.first});
            }
        }
    }

    for(int i = 2; i <= n; i++)
        cout << dist[i] << " "; 
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);

    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y, cost;
        cin >> x >> y >> cost;
        v[x].push_back({y, cost});
    }
    
    bfs();
}