#define MAX_N 50000

#include <fstream>
#include <vector>
#include <queue>
using namespace std;

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

struct A
{
    int nod, cost;

    bool operator > (const A& other) const { return cost < other.cost; }
};

int n, m;
vector<A> G[MAX_N + 1];
vector<int> dist;

void Citire();
void Dijkstra(int nodStart, vector<int>& outDist);

int main()
{
    Citire();
    Dijkstra(1, dist);

    for (size_t i = 2, l = dist.size(); i < l; ++i)
    {
        fout << dist[i] << ' ';
    }

    fin.close();
    fout.close();
    return 0;
}

void Citire()
{
    fin >> n >> m;

    int x, y, cost;
    for (int i = 0; i < m; ++i)
    {
        fin >> x >> y >> cost;
        G[x].push_back({ y, cost });
        G[y].push_back({ x, cost });
    }
}

void Dijkstra(int nodStart, vector<int>& outDist)
{
    outDist = vector<int>(n + 1, -1);
    outDist[nodStart] = 0;

    priority_queue<A, vector<A>, greater<A>> Q;
    for (const auto& i : G[nodStart])
    { Q.push({ i.nod, i.cost }); outDist[i.nod] = i.cost; }

    while (!Q.empty())
    {
        A nod = Q.top();
        Q.pop();

        for (const auto& i : G[nod.nod])
        {
            if ((outDist[i.nod] == -1) || (outDist[i.nod] > (i.cost + outDist[nod.nod])))
            {
                outDist[i.nod] = i.cost + outDist[nod.nod];
                Q.push({ i.nod, outDist[i.nod] });
            }
        }
    }
}