#include <fstream>
#define INF 2000000000
#define limN 50001
#define limM 250001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
//struct heap {int cost, a, b;} v[limN]; //minheap (nh = nr de elem)
int nr, n, m, nh, cost, vf[limM], urm[limM], lst[limN], D[limN], h[limN], c[limM], pred[limN], poz[limN];
bool viz[limN];
//poz[i] = repr pozitia la care se afla i in heap;
//c[] = costuri citite
//d[] = costuri minime
//pred[] = vector de tati
void schimba (int x, int y)
{
    int aux = h[x];
    h[x] = h[y];
    h[y] = aux;
    poz[h[x]] = x; //poz in heap pe care se afla elementul aflat pe poz x in heap este x (da, chiar asa)
    poz[h[y]] = y;
}

void urca(int poz)
{
    while (h[poz] < h[poz/2] && poz > 1)
    {
        schimba(poz, poz/2);
        poz/=2;
    }
}

void coboara(int p)
{
    int bun=p, fs=2*p, fd=2*p+1;
    if(fs<=nh && D[h[fs]]<D[h[bun]])
        bun=fs;
    if(fd<=nh && D[h[fd]]<D[h[bun]])
        bun=fd;
    if(bun!=p)
    {
        schimba (bun, p);
        coboara(bun);
    }
}

void sterge(int x)
{
    schimba (x, nh);
    --nh;
    coboara(x);
}

void adauga (int x, int y, int cost) //adaug pe y in lista lui x
{
    ++nr;
    vf[nr]=y;
    urm[nr] = lst[x];
    c[nr] = cost;
    lst[x]=nr;
}

void parc (int x)
{
    int p = lst[x];
    while(p) //pt fiecare vecin al lui x
    {
        int y = vf[p]; //y = val nodului vecin lui x
        if (D[x]+c[p] < D[y] && !viz[y]) //daca dist de la radacina la x + costul muchiei p (muchia x -> y) este
        {                     //mai mic decat dist de la rad la y (initial infinit)
            D[y] = D[x] + c[p];
            pred[y] = x;
            urca(poz[y]);
        }
        p=urm[p];
    }
}

int main()
{
    int a, b;
    f >> n >> m;
    for (int i=1; i<=m; ++i)
    {
        f >> a >> b >> cost;
        adauga(a, b, cost); //construiesc listele de adiacenta
        //c[i] = cost;
    }

    nh = n; //in heap pun toate nodurile
    for (int i=1; i<=n; ++i)
        h[i] = i, poz[i] = i;

    D[1] = 0;
    for (int i=2; i<=n; ++i)
        D[i] = INF;

    while (nh)
    {
        int x = h[1]; //iau nodul cu dist minima fata de ...
        sterge (1);
        poz [x] = -1; //poz la care se afla x in heap nu mai exista
        viz[x] = 1; //ma pot folosi si de poz[] ca vect de vizitati
        parc(x);
    }

    for (int i=2; i<=n; ++i)
        if (D[i]==INF)
            g << 0 << " ";
        else
            g << D[i] << " ";

}