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

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

int noduri, legaturi, a, b, c, contor, cost[50004], facut[50004], vecin;

struct Heap
{
    int nod, cost;
}heap[200004], curent;

struct Lista
{
    int nod, cost;
};
vector <Lista> lista[200004];

void urca(int poz)
{
    while(poz/2 > 0 && heap[poz/2].cost > heap[poz].cost)
    {
        swap(heap[poz/2], heap[poz]);
        poz /= 2;
    }
}

void adauga(int nod, int cost)
{
    contor++;
    heap[contor].nod = nod;
    heap[contor].cost = cost;
    urca(contor);
}

void coboara(int poz)
{
    poz *= 2;
    while(poz <= contor)
    {
        if(heap[poz].cost > heap[poz+1].cost && poz+1 <= contor)
        poz++;

        if(heap[poz/2].cost > heap[poz].cost)
        {
            swap(heap[poz/2], heap[poz]);
            poz *= 2;
        }
        else
        break;
    }
}

Heap scoate()
{
    Heap copie = heap[1];
    heap[1] = heap[contor];
    coboara(1);
    return copie;
}

int main()
{
    cin >> noduri >> legaturi;
    for(int i=1; i <= legaturi; i++)
    {
        cin >> a >> b >> c;
        lista[a].push_back({b, c});
    }
    for(int i=1; i <= noduri; i++)
    {
        cost[i] = 1000000000;
    }
    cost[1] = 0;
    adauga(1, 0);

    for(int yy=2; yy <= noduri; yy++)
    {
        do
        {
            curent = scoate();
        }while(facut[curent.nod] == 1);

        facut[curent.nod] = curent.cost+1;
        for(int i=0; i < lista[curent.nod].size(); i++)
        {
            vecin = lista[curent.nod][i].nod;
            if(facut[vecin] == 0 && cost[vecin] > cost[curent.nod]+lista[curent.nod][i].cost)
            {
                cost[vecin] = cost[curent.nod]+lista[curent.nod][i].cost;
                adauga(vecin, cost[vecin]);
            }
        }
    }
    for(int i=2; i <= noduri; i++)
    {
        cout << cost[i] << ' ';
    }
}