#include <bits/stdc++.h>
using namespace std;
struct elem
{
    int nod, cost;
    bool operator <(const elem &other) const
    {
        return cost > other.cost;
    }
};
priority_queue <elem> Q;
vector <elem> v[50005];
int dist[50005], n, m, i, x, y, z;
void dijkstra(int node)
{
    Q.push({1, 0});
    while(!Q.empty())
    {
        int node = Q.top().nod;
        int cost = Q.top().cost;
        Q.pop();
        if(dist[node] == INT_MAX) dist[node] = cost;
        cost = dist[node];
        for(int i = 0; i < v[node].size(); i++)
            if(dist[v[node][i].nod] > v[node][i].cost + cost)
                Q.push({v[node][i].nod, v[node][i].cost + cost});
    }
}
int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f >> n >> m;
    for(i = 1; i <= m; i++)
    {
        f >> x >> y >> z;
        v[x].push_back({y, z});
    }
    for(i = 1; i <= n; i++)
        dist[i] = INT_MAX;
    dijkstra(1);
    for(i = 2; i <= n; i++)
        g << dist[i] << " ";
    return 0;
}