#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

#define NMAX 50015
#define oo (1<<30)
#define Gnode first
#define Gcost second
#define CMP(a,b) (Dist[Heap[a]]<Dist[Heap[b]])

int Heap[NMAX];
int Dist[NMAX];
int Pos[NMAX]; //Pos[i] > 0 => pozitia in Heap
               //Pos[i] == 0 => nod inca neadaugat in Heap
               //Pos[i] < 0 => nod calculat

vector < pair < int , int > > G[NMAX];

int N,M;
int HeapVaf;

inline int father(int node){
    return node>>1;
}

inline int left_son(int node){
    return node<<1;
}

inline int right_son(int node){
    return (node<<1)+1;
}

void sift(int node)
{
    int son;

    do{
        son = 0;
        if(left_son(node) <= HeapVaf)
        {
            son = left_son(node);

            if(right_son(node) <= HeapVaf && CMP(right_son(node),left_son(node)))
                son = right_son(node);
            if(!CMP(son,node))
                son = 0;
        }

        if(son)
        {
            swap(Heap[node],Heap[son]);
            swap(Pos[Heap[node]],Pos[Heap[son]]);
            node = son;
        }
    }while(son);
}

void percolate(int node)
{
    while(node>1 && CMP(node,father(node)))
    {
        swap(Heap[node],Heap[father(node)]);
        swap(Pos[Heap[node]],Pos[Heap[father(node)]]);
        node = father(node);
    }
}

void Read()
{
    freopen("dijkstra.in","r",stdin);

    scanf("%d%d",&N,&M);
    for(int i=1,x,y,z;i<=M;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        G[x].push_back(make_pair(y,z));
    }
}

void Dijkstra()
{
    Heap[++HeapVaf] = 1;
    Pos[1] = 1;

    while(HeapVaf)
    {
        int node = Heap[1];
        Pos[node] = -1;
        Heap[1] = Heap[HeapVaf--];
        Pos[Heap[1]] = 1;
        sift(1);

        for(vector < pair < int , int > > :: iterator it = G[node].begin(); it != G[node].end(); ++ it )
        {
            if(!Pos[(*it).Gnode])
            {
                Heap[++HeapVaf] = (*it).Gnode;
                Pos[(*it).Gnode] = HeapVaf;
                Dist[(*it).Gnode] = Dist[node] + (*it).Gcost;
                percolate(HeapVaf);
            }
            else
                if(Dist[node] + (*it).Gcost < Dist[(*it).Gnode])
                {
                    Dist[(*it).Gnode] = Dist[node] + (*it).Gcost;
                    percolate(Pos[(*it).Gnode]);
                }
        }
    }
}

void Print()
{
    freopen("dijkstra.out","w",stdout);

    for(int i=2;i<=N;i++)
        printf("%d ",Dist[i]);
}

int main()
{
    Read();
    Dijkstra();
    Print();
    return 0;
}