#include <stdio.h>
#define fisier "graf.in"
#define inf 1 << 15

    struct heap_min
    {
        int key,nod;
    }   heap[100];

    int nr,poz[100],ad[100][100],d[100],tata[100];
    int n,m,first;
        // n: nr de elemente din heap
        // poz[x]: pozitia elementului x in heap.

void minheap(int nod) //mentine proprietatea de min heap
{
        int st=2*nod, dr=2*nod+1, max = -1;
        heap_min aux;
        if (st<=nr && heap[st].key < heap[nod].key)
                max=st;
        if (dr<=nr && heap[dr].key < heap[max].key)
                max=dr;
        if (max != -1 )
        {
                aux=heap[nod];
                heap[nod] = heap[max];
                heap[max] = aux;
                poz[heap[nod].nod]=nod;
                poz[heap[max].nod]=max;
                minheap(max);
        }
}

void push ( int v ) //insereaza elementul v in heap
{
        heap_min aux;
        heap[++nr].key = d[v];
        heap[nr].nod = v;
        poz[v] = nr;
        for (int i=nr; i>1; i= i>>1 )
                if (heap[i >> 1].key > heap[i].key)
                {
                    aux=heap[i >> 1];
                    heap[i >> 1] = heap[i];
                    heap[i] = aux;
                    poz[heap[i >> 1].nod]=i >> 1;
                    poz[heap[i].nod] = i;
                }
}

int pop () // scoate elementul minim din heap
{
        int rez = heap[1].nod;
        heap[1] = heap[nr--];
        poz[heap[nr+1].nod]=1;
        minheap(1);
        return rez;
}

void decrease(int x,int y) // schimba valoarea nodului x din heap in y
{
    heap[x].key=y;
    minheap(1);
}

void init_ad() // initializeaza matricea
{
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
            ad[i][j]=inf;
        ad[i][i]=0;
    }
}

void citire() // citire ?!
{
    freopen(fisier,"r",stdin);
    scanf("%d %d",&n,&m);
    init_ad();
    for (int i=0;i<m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        ad[x][y]=z;
    }
    //scanf("%d",&first);
    fclose(stdin);
}


void init()
{
    first=1;
    for (int i=1;i<=n;i++)
    if (i != first)
    {
        d[i]=ad[first][i];
        tata[i]=first;
        push(i);
    }

}

void dijkstra()
{
    while (nr)
    {
        int v=pop();
        for (int i=1;i<=n;i++)
            if (ad[v][i] != inf && v != i)
            {
                if (d[i] > d[v]+ad[v][i])
                {
                    d[i] = d[v]+ad[v][i];
                    tata[i]=v;
                    decrease(i,d[i]);
                }
            }
    }
}

void drum(int x)
{
    if (tata[x] != first) drum(tata[x]);
    printf(" -> %d ",x);
}

int main()
{

    citire();
    init();
    dijkstra();
    for (int i=2;i<=n;i++)
    printf("%d ",d[i]); /*
    if ( i!= first )
    {
        printf("To %d: %d ",i,d[i]);
        printf("( %d ",first);
        drum(i);
        printf(")\n");
    } */
	return 0;
}