#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#define NMax 50000
#define inf 1001

using namespace std;

fstream fin("dijkstra.in",ios::in);
fstream fout("dijkstra.out",ios::out);

struct element{int nod; double cost;};//heapul are ca informatii nodul si costul nodului respectiv

struct arc{int edge,cost;};//retin informatiile ca lista de succesori

typedef element Heap[NMax];

Heap H;
arc *A[NMax];
int n,poz[NMax],x0=1,N;
//vectorul "poz" tine minte pozitia pe care se afla nodul x in heap
//A - lista de succesori
//n - numarul de noduri
//H - heap care tine minte distantele de la x0 la H[i].nod cat si costul distantei H[i].cost
//x0 - nod de start
inline int father(int k)
{
    return k/2;
}

inline int left_son(int k)
{
    return 2*k;
}

inline int right_son(int k)
{
    return 2*k+1;
}

void percolate(int n,int k)
{
    while(k>1&&H[father(k)].cost>H[k].cost)
    {
        swap(poz[H[father(k)].nod],poz[H[k].nod]);
        //poz[H[father(k)].nod]=H[k].nod;
        //poz[H[k].nod]=H[father(k)].nod;
        swap(H[k],H[father(k)]);
        k=father(k);
    }
}

void sift(int n,int k)
{
    int son;
    do
    {
        son=0;
        //alege un fiu mai mic ca tatal
        if(left_son(k)<=n)
        {
            son=left_son(k);
            if(right_son(k)<=n&&H[right_son(k)].cost<H[left_son(k)].cost)
                son=right_son(k);
            if(H[son].cost>H[k].cost)
                son=0;
        }
        if(son)
        {
            poz[H[k].nod]=son;
            poz[H[son].nod]=k;
            swap(H[k],H[son]);
            k=son;
        }
    }while(son);
}

void Build_Heap()
{
    for(int i=n/2;i>0;i--)
        sift(n,i);
}


void Elimina_minim()
{
    swap(poz[H[1].nod],poz[H[n].nod]);
    poz[H[1].nod]*=(-1);
    swap(H[1],H[n]);

    n--;
    sift(n,1);
}


void Read()
{
    int x,y,c,i,m;
    fin>>n>>m;
    N=n;//N tine minte numarul de noduri pt ca n se modifica in lucrul cu heapul
    for(i=1;i<=n;i++)
    {
        //aloc memorie pt A - start
        A[i]=(arc*)realloc(A[i],sizeof(arc));
        A[i][0].edge=0;//retine numarul de noduri adiacente cu x
        //aloc memorie pt A - sfarsit

        //initializare
        poz[i]=i;
        H[i].cost=inf;
        H[i].nod=i;
    }

    while(m--)
    {
        fin>>x>>y>>c;
        A[x][0].edge++;
        A[x]=(arc*)realloc(A[x],(A[x][0].edge+1)*sizeof(arc));
        A[x][A[x][0].edge].edge=y;
        A[x][A[x][0].edge].cost=c;
    }

    H[x0].nod=x0;
    H[x0].cost=0;

    for(i=1;i<=A[x0][0].edge;i++)
        {
            H[A[x0][i].edge].cost = A[x0][i].cost;
        }

    //build H as a Heap
    Build_Heap();

    //elimint pe x0 din heap
    Elimina_minim();
}

void Update(int k)
{
    int nod_in_heap=poz[k];

    if(k>1&&H[nod_in_heap].cost<H[father(nod_in_heap)].cost)
        percolate(n,nod_in_heap);
    else sift(n,nod_in_heap);
}

void Dijkstra_Heap()
{
    double dMin;
    int VfMin,i;

    while(n)
    {
        dMin=H[1].cost;
        VfMin=H[1].nod;
        Elimina_minim();
        //am gasit minim si l-am eliminat

        //acum pot actualiza nodurile
        for(i=1;i<=A[VfMin][0].edge;i++)
        {
            if((poz[A[VfMin][i].edge]>0)&&((dMin+A[VfMin][i].cost)<H[poz[A[VfMin][i].edge]].cost))//daca poz e -1 inseamna ca nodul a fost ales deja ca minim
                {
                    H[poz[A[VfMin][i].edge]].cost=dMin+A[VfMin][i].cost;
                    Update(A[VfMin][i].edge);
                }
        }
    }
}

void Write()
{
    for(int i=2;i<=N;i++)
        {
            if(H[abs(poz[i])].cost!=inf)
                fout<<H[abs(poz[i])].cost<<" ";
            else fout<<"0 ";
        }

}

int main()
{
    Read();

    Dijkstra_Heap();

    Write();

    return 0;
}