#include <bits/stdc++.h>
#define Mmax 250002
#define Nmax 50002
#define oo Mmax * 1000 + 10
FILE *fin = freopen("dijkstra.in", "r", stdin);
FILE *fout = freopen("dijkstra.out", "w", stdout);

using namespace std;
int H[Mmax], n, m, vf[Mmax], urm[Mmax], lst[Nmax], len[Mmax];
int d[Nmax];
void add(int x, int y, int z)
{
    vf[++ vf[0]] = y;
    urm[vf[0]] = lst[x];
    lst[x] = vf[0];
    len[vf[0]] = z;
}
int right_son(int x)
{
    return 2 * x + 1;
}
int left_son(int x)
{
    return 2 * x;
}
int father(int x)
{
    return x / 2;
}
void bubbling_up()
{
    int K = H[0];
    int key = H[K];
    while ((K > 1) && (d[key] < d[H[father(K)]]))
    {
        H[K] = H[father(K)];
        K = father(K);
    }
    H[K] = key;
}
void bubbling_down()
{
    int son, K = 1;
    do
    {
        son = 0;
        int lson = left_son(K);
        int rson = right_son(K);
        if (lson <= H[0])
        {
            son = lson;
            if (rson <= H[0] && d[H[rson]] < d[H[son]])
            {
                son = rson;
            }
            if (d[H[son]] >= d[H[K]])
            {
                son = 0;
            }
        }
        if (son)
        {
            swap(H[K], H[son]);
            K = son;
        }
    }
    while (son);
}
void extract_H()
{
    H[1] = H[H[0]];
    -- H[0];
    bubbling_down();
}
void insert_H(int x)
{
    H[++ H[0]] = x;
    bubbling_up();
}
void read()
{
    int x, y, z;
    scanf("%d %d", &n, &m);
    while(m --)
    {
        scanf("%d %d %d", &x, &y, &z);
        add(x, y, z);
    }
}
void dijkstra()
{
    int x, y;
    memset(d, oo, sizeof(d));
    /// source
    d[1] = 0, H[++ H[0]] = 1;

    while(H[0])
    {
        x = H[1];
        extract_H();
        y = lst[x];
        while(y)
        {
            if(d[vf[y]] > d[x] + len[y])
            {
                d[vf[y]] = d[x] + len[y];
                insert_H(vf[y]);
            }
            y = urm[y];
        }
    }
}
void write()
{
    for(int i = 2; i <= n; ++ i)
        printf("%d ", d[i] == oo ? 0 : d[i]);
}
int main()
{
    read();
    dijkstra();
    write();
    return 0;
}