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

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

int nr, drumuri, contor, poz, a, b, c, cost[50005], viz[50005], curent;

struct list
{
    int dest, cost;
}urm;
vector <list> lista[50005];

struct hep
{
    int nod, cost;
}heap[300004];

void adauga(int nod, int cost)
{
    contor++;
    poz = contor;
    while(contor / 2 > 0 && heap[contor/2].cost > cost)
    {
        heap[poz] = heap[poz/2];
        poz /= 2;
    }
    heap[poz].nod = nod;
    heap[poz].cost = cost;
}

int scoate()
{
    if(contor <= 0)
    return -1;

    int tine = heap[1].nod;
    heap[1] = heap[contor];
    contor--;

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

        if(heap[poz/2].cost > heap[poz].cost)
        {
            swap(heap[poz/2], heap[poz]);
            poz = poz/2;
        }
        else
        break;
    }
    if(viz[tine] == 0)
    return tine;
    return scoate();
}

int main()
{
    cin >> nr >> drumuri;
    for(int yy=1; yy <= drumuri; yy++)
    {
        cin >> a >> b >> c;
        lista[a].push_back({b,c});
    }
    for(int i=0; i <= 50001; i++)
    cost[i] = -1;

    viz[1] = 1;
    curent = 1;
    cost[1] = 0;

    while(curent != -1)
    {
        for(int i=0; i < lista[curent].size(); i++)
        {
            urm = lista[curent][i];
            if(viz[urm.dest] == 0 && (cost[urm.dest] == -1 || urm.cost + cost[curent] < cost[urm.dest]))
            {
                cost[urm.dest] = urm.cost + cost[curent];
                adauga(lista[curent][i].dest, cost[curent]+lista[curent][i].cost);
            }
        }
        curent = scoate();
    }

    for(int i=2; i <= nr; i++)
    {
        if(cost[i] != -1)
        cout << cost[i] << ' ';
        else
        cout << 0 << ' ';
    }
}