#include <bits/stdc++.h>
#define Nmax 50005
using namespace std;
struct dij
{
    int nod, cost;
    bool operator <(const dij& other) const
    {
        return cost > other.cost;
    }
};
vector <dij> Numbers[Nmax];
priority_queue <dij> Q;
int Distanta[Nmax], n, m, i, x, y, val;
bool Visited[Nmax];
void Dijkstra(int x)
{
    int Vecin, Cost, Nod;
    Q.push({ x, 0 });
    Visited[x] = true;
    while (!Q.empty())
    {
        Nod = Q.top().nod;
        Q.pop();
        Visited[Nod] = false;
        for (int i = 0; i < Numbers[Nod].size(); ++i)
        {
            Vecin = Numbers[Nod][i].nod;
            Cost = Numbers[Nod][i].cost;
            if (Distanta[Nod] + Cost < Distanta[Vecin])
            {
                Distanta[Vecin] = Distanta[Nod] + Cost;
                Q.push({ Vecin, Distanta[Vecin] });
            }
        }

    }
}

int main()
{
    ifstream f("dijkstra.in");
    ofstream g("dijkstra.out");
    f >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        f >> x >> y >> val;
        Numbers[x].push_back({ y, val });
    }
    Distanta[1] = 0;
    for (int i = 2; i <= n; ++i)
        Distanta[i] = 1e9;
    Dijkstra(1);
    for (int i = 2; i <= n; ++i)
        if (Distanta[i] != 1e9) g << Distanta[i] << " ";
        else g << 0 << " ";
    return 0;
}