#include <bits/stdc++.h>
#define in "dijkstra.in"
#define out "dijkstra.out"
#define INF 0x3f3f3f3f
#define MN 50005
using namespace std;
struct nod
{
    int vf, cost;
    nod *next;
};
typedef nod *graf;
graf A[MN];
int D[MN], H[MN], Poz[MN], N, M, k;

void add(int srs, int vf, int cost)
{
    graf p = new nod;
    p->vf = vf;
    p->cost = cost;
    p->next = A[srs];
    A[srs] = p;
}

void read_in()
{
    assert(freopen(in, "r", stdin));
    assert(scanf("%d%d", &N, &M));
    for(int a, b, c; M; --M)
    {
        assert(scanf("%d%d%d", &a, &b, &c));
        add(a, b, c);
    }
    fclose(stdin);
}

void heap_sift(int poi)
{
    int cp;
    while(poi <= k)
    {
        cp = poi<<1;
        if(cp <= k)
        {
            if(cp+1 <= k && D[cp] > D[cp+1])
                cp++;
        }
        else return;

        if(D[poi] > D[cp])
        {
            Poz[H[poi]] = cp;
            Poz[H[cp]] = poi;
            swap(poi, cp);
            poi = cp;
        }
        else return;
    }
}

void heap_percolate(int poi)
{
    while(poi > 1)
    {
        int ft = poi>>1;
        if(D[poi] > D[ft])
        {
            Poz[H[poi]] = ft;
            Poz[H[ft]] = poi;
            swap(H[poi], H[ft]);
            poi = ft;
        }
        else return;
    }
}

void dijkstra()
{
    D[0] = 0;
    for(int i = 2; i <= N; ++i)
        D[i] = INF, Poz[i] = -1;
    H[1] = Poz[1] = 1;
    k = 1;
    while(k)
    {
        int pmc = H[1];
        swap(H[1], H[k]);
        Poz[H[k]] = 1;
        k--;
        heap_sift(1);

        graf q = A[pmc];
        while(q)
        {
            if(D[q->vf] > D[pmc] + q->cost)
            {
                D[q->vf] = D[pmc] + q->cost;
                if(Poz[q->vf] == -1)
                {
                    H[++k] = q->vf;
                    Poz[H[k]] = k;
                    heap_percolate(k);
                }
                else heap_percolate(Poz[q->vf]);
            }
            q = q->next;
        }
    }
}

void print_out()
{
    assert(freopen(out, "w", stdout));
    for(int i = 2; i <= N; ++i)
        assert(printf("%d ", *(D+i)));
    fclose(stdout);
}

int main()
{
    read_in();
    dijkstra();
    print_out();
    return 0;
}