#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int INF = 0x3F3F3F3F;
int dist[50002];

struct el {
    int nod, cost;

    bool operator < (const el &other) const
    {
        return cost > other.cost;
    }
};
priority_queue<el> pq;
vector<el> a[50002];

void dijkstra (int source)
{
    pq.push({source, 0});
    dist[source] = 0;

    while (!pq.empty())
    {
        el x = pq.top();
        pq.pop();
        if (dist[x.nod] == x.cost)
        {
            for (el y : a[x.nod])
                if (dist[y.nod] > dist[x.nod] + y.cost)
                {
                    dist[y.nod] = dist[x.nod] + y.cost;
                    pq.push({y.nod, dist[y.nod]});
                }
        }
    }
}

int main () {
    int n, m, x, y, cost;
    fin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        fin >> x >> y >> cost;
        a[x].push_back({y, cost});
    }
    for (int i = 1; i <= n; i++)
        dist[i] = INF;
    dijkstra (1);

    for (int i = 2; i <= n; i++)
        fout << dist[i] << ' ';
}