#include <fstream>
#define INF 999999999
#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];
//poz[i] = pozitiile din heap
//c[] = costuri citite
//d[] = costuri minime
void schimba (int x, int y)
{
    int aux = h[x];
    h[x] = h[y];
    h[y] = aux;
    poz[h[x]] = x;
    poz[h[y]] = y;
}

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

void coboara(int p)
{
    int bun=p, fs=2*p, fd=2*p+1;
    if(fs<=nh && h[fs]<h[bun])
        bun=fs;
    if(fd<=nh && h[fd]<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)
    {
        int y = vf[p];
        if (D[x]+c[p] < D[y])
        {
            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;
    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];
        sterge (1);
        poz [x] = -1; //poz la care se afla x in heap
        parc(x);
    }

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

}