#include <bits/stdc++.h>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m, d[50003], viz[50003];
struct elem
{
    int nod, cost;
    bool operator<(const elem A) const
    {
        return A.cost < cost;
    }
};
vector<elem> L[50003];
priority_queue<elem> Q;

void Citire()
{
    int i, x, y, c;
    fin >> n >> m;
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        L[x].push_back({ y, c });
    }
}

void Dijkstra(int sursa)
{
    int i, j, x, k, kcost;
    for (i = 1; i <= n; i++)
        d[i] = 2e9;
    Q.push({ sursa, 0 });
    d[sursa] = 0;
    while (!Q.empty())
    {
        k = Q.top().nod;
        kcost = Q.top().cost;
        cout << k << ' ';
        Q.pop();
        viz[k] = 1;
        for (auto e : L[k])
        {
            if (viz[e.nod] == 0)
                if (d[e.nod] > d[k] + e.cost)
                {
                    d[e.nod] = d[k] + e.cost;
                    Q.push({ e.nod, e.cost });  
                }
        }
    }
    for (i = 2; i <= n; i++)
        fout << d[i] << ' ';
}

int main()
{
    Citire();
    Dijkstra(1);
    fin.close();
    fout.close();
    return 0;
}