#include <fstream>

using namespace std;

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

const int N = 50001, M = 250001, INF = 1e9;

int h[N], v[N], poz[N], nh, vf[M], urm[M], cst[M], lst[N], viz[N], nr, d[N];
int n, m, x, y, z;

void adauga_graf(int x, int y, int z)
{
    vf[++nr] = y;
    cst[nr] = z;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void schimb(int p, int q)
{
    swap(h[p], h[q]);
    poz[h[p]] = p;
    poz[h[q]] = q;
}

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

void adauga(int p)
{
    h[++nh] = p;
    poz[p] = nh;
    urca(nh);
}

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

void sterge(int p)
{
    p = poz[p];
    schimb(p, nh--);
    urca(p);
    coboara(p);
}

void dijkstra()
{
    for(int i = 2; i <= n; i++)
        d[i] = INF;
    for(int i = 1; i <= n; i++)
        adauga(i);

    while(nh > 0)
    {

        int x = h[1];
        sterge(x);
        for(int p = lst[x]; p != 0; p = urm[p])
        {
            int y = vf[p];
            if(d[x] + cst[p] < d[y])
            {
                d[y] = d[x] + cst[p];
                urca(poz[y]);
            }
        }


    }


}



int main()
{

    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        in >> x >> y >> z;
        adauga_graf(x, y, z);
    }
    dijkstra();
    for(int i = 2; i <= n; i++)
    {
        //if(d[i] < INF)
        out << d[i] << " ";
        //else out << 0 << " ";
    }
    return 0;
}