#include<stdio.h>
using namespace std;
const int N = 50005, M = 250005, INF = 1000000000;
int vf[M], lst[N], urm[M], m = 0, cost[M], viz[N], h[N], poz[N], d[N], nh;
void adauga (int x, int y, int c)
{
    vf[++m] = y;
    cost[m] = c;
    urm[m] = lst[x];
    lst[x] = m;
}
void schimba (int p1, int p2)
{
    int aux = h[p1];
    h[p1] = h[p2];
    h[p2] = aux;
    poz[h[p1]] = p1;
    poz[h[p2]] = p2;
}
void urca (int p)
{
    while (p > 1 && d[h[p]] < d[h[p / 2]])
    {
        schimba (p, p / 2);
        p /= 2;
    }
}
void coboara (int p)
{
    int fS = p * 2, fD = p * 2 + 1, bun = p;
    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);
    }
}
int main ()
{
    FILE *in, *out;
    in = fopen ("dijkstra.in", "r");
    out = fopen ("dijkstra.out", "w");
    int n, m2;
    fscanf (in, "%d%d", &n, &m2);
    int i, c, x, y;
    for (i = 1; i <= m2; i++)
    {
        fscanf (in, "%d%d%d", &x, &y, &c);
        adauga (x, y, c);
    }
    for (i = 1; i <= n; i++)
    {
        d[i] = INF;
        poz[i] = i;
        h[i] = i;
    }
    d[1] = 0;
    nh = n;
    int p;
    while (nh != 0)
    {
        x = h[1];
        schimba (1, nh--);
        p = lst[x];
        coboara (1);
        while (p != 0)
        {
            y = vf[p];
            c = cost[p];
            if (c + d[x] < d[y])
            {
                d[y] = c + d[x];
                urca (poz[y]);
            }
            p = urm[p];
        }
    }
    for (i = 2; i <= n; i++)
    {
        if (d[i]  != INF)
            fprintf (out, "%d ", d[i]);
        else
            fprintf (out, "0 ");
    }
    return 0;
}