#include<stdio.h>
#include<vector>
#define MAXV 50000
#define MAXE 250000
#define INF 1000000000
void init();
void dijkstra();
int left_son(int nod);
int right_son(int nod);
int father(int nod);
void add(int x);
void rmv(int nod);
void sift(int nod);
void percolate(int nod);
void swap_nodes(int nod1,int nod2);
FILE*fin,*fout;
struct Edge
{
    int dst;
    int cost;
};
Edge edges[MAXE+1];
std::vector<int> neighbors[MAXV+1];
int shortestPath[MAXV+1];
int heap[MAXV+1];
int poz[MAXV+1];
int N=0;
int E,V;
int main()
{
    fin=fopen("dijkstra.in","r");
    fout=fopen("dijkstra.out","w");
    fscanf(fin,"%d%d",&V,&E);
    for(int i=1;i<=E;i++)
    {
        int src,dst,cst;
        fscanf(fin,"%d%d%d",&src,&dst,&cst);
        neighbors[src].push_back(i);
        edges[i].dst=dst;
        edges[i].cost=cst;
    }
    init();
    dijkstra();
    for(int i=2;i<=V;i++)
    {
        fprintf(fout,"%d ",shortestPath[i]);
    }
    fclose(fin);
    fclose(fout);
}
void init()
{
    shortestPath[1]=0;
    heap[1]=1;
    poz[1]=1;
    for(int i=2;i<=V;i++)
    {
        shortestPath[i]=INF;
        heap[i]=i;
        poz[i]=i;
    }
    N=V;
}
int left_son(int nod)
{
    return 2*nod;
}
int right_son(int nod)
{
    return 2*nod+1;
}
int father(int nod)
{
    return nod/2;
}
void rmv(int nod)
{
    swap_nodes(nod,N);
    N--;
    if(nod >1 && shortestPath[heap[nod]] < shortestPath[heap[father(nod)]])
    {
        percolate(nod);
    }
    else
    {
        sift(nod);
    }
}
void sift(int nod)
{
    int son;
    do
    {
        son=0;
        if(right_son(nod)<=N)
        {
            if(shortestPath[heap[left_son(nod)]] < shortestPath[heap[right_son(nod)]])
            {
                son=left_son(nod);
            }
            else
            {
                son=right_son(nod);
            }
        }
        else if(left_son(nod)<=N)
        {
            son=left_son(nod);
        }
        if(shortestPath[heap[son]] > shortestPath[heap[nod]])
        {
            son=0;
        }
        if(son)
        {
            swap_nodes(nod,son);
            nod=son;
        }
    }while(son);
}
void percolate(int nod)
{
    while(nod>1 && shortestPath[heap[nod]] < shortestPath[heap[father(nod)]])
    {
        swap_nodes(nod,father(nod));
        nod=father(nod);
    }
}
void swap_nodes(int nod1,int nod2)
{
    std::swap(heap[nod1],heap[nod2]);
    std::swap(poz[heap[nod1]],poz[heap[nod2]]);
}
void dijkstra()
{
    while(N>0)
    {
        int currentNode=heap[1];
        for(int i=0;i<neighbors[currentNode].size();i++)
        {
            int muchie=neighbors[currentNode][i];
            if(shortestPath[edges[muchie].dst] > shortestPath[currentNode] + edges[muchie].cost)
            {
                shortestPath[edges[muchie].dst]= shortestPath[currentNode] + edges[muchie].cost;
                percolate(poz[edges[muchie].dst]);
            }
        }
        rmv(1);
    }
}