#include <fstream>
#include <vector>
#include <memory.h>

#define Max 1000000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct heapuri
{
    int nod,lg;
} heap[500010],tmp;

int n,m,i,j,act[50010],x,y,lg,nod;

vector<heapuri> a[50010];

void AddToHeap(int nod,int lg)
{
    int thislg=++heap[0].lg;
    int parent=thislg/2;
    while(lg<heap[parent].lg)
    {
        heap[thislg].lg=heap[parent].lg;
        heap[thislg].nod=heap[parent].nod;
        thislg=parent;
        parent=thislg/2;
    }


    heap[thislg].lg=lg;
    heap[thislg].nod=nod;
}


void RemoveFromHeap()
{
    heap[0].lg--;

    heap[1].lg=heap[heap[0].lg+1].lg;
    heap[heap[0].lg+1].lg=Max;
    heap[1].nod=heap[heap[0].lg+1].nod;



    int thislg=1;
    int child=thislg*2;

    while((heap[thislg].lg>heap[child].lg || heap[thislg].lg>heap[child+1].lg )&& thislg<heap[0].lg)
    {
        if(heap[child].lg<heap[child+1].lg)
        {

            tmp.lg=heap[thislg].lg;
            tmp.nod=heap[thislg].nod;
            heap[thislg].lg=heap[child].lg;
            heap[thislg].nod=heap[child].nod;
            heap[child]=tmp;
            thislg=child;
            child=thislg*2;
        }
        else
        {


            tmp.lg=heap[thislg].lg;
            tmp.nod=heap[thislg].nod;
            heap[thislg].lg=heap[child+1].lg;
            heap[thislg].nod=heap[child+1].nod;
            heap[child+1]=tmp;

            thislg=child+1;
            child=thislg*2;
        }
    }

}


int main()
{
    fin>>n>>m;

    for(i=1; i<=m; i++)
        heap[i].lg=Max;

    for(i=1; i<=m; i++)
    {
        fin>>x>>y>>lg;

        tmp.nod=y;
        tmp.lg=lg;

        a[x].push_back(tmp);


    }


    heap[0].lg=1;
    heap[1].nod=1;
    heap[1].lg=0;


    while(heap[0].lg )
    {

        nod=heap[1].nod;
        lg=heap[1].lg;
        if(act[nod]==0)
        {
            act[nod]=lg;

            for(i=0; i<a[nod].size(); i++)
            {
                if(act[a[nod][i].nod]==0 && a[nod][i].nod!=1)
                {
                    AddToHeap(a[nod][i].nod,lg+a[nod][i].lg);
                }
            }
        }
        RemoveFromHeap();

    }

    for(i=2; i<=n; i++)
    {
        fout<<act[i]<<' ';
    }

    return 0;
}