#include<stdio.h>
#include<vector>
#include<limits.h>
using namespace std;
#define nrn 50005
#define inf INT_MAX
#define lfs(x) (x*2)
#define rts(x) (x*2+1)
#define father(x) (x/2)

struct node{int nr,val;};
vector<node>V[nrn];
int k,n,aux,h[nrn],poz[nrn],D[nrn];

FILE *in=fopen("dijkstra.in","r"),*out=fopen("dijkstra.out","w");

void upheap(int i)
{
    int tata;
    while(i>1)
    {
        tata=father(i);
        if(D[h[tata]]>D[h[i]])
        {
            poz[h[i]]=tata;
            poz[h[tata]]=i;
            aux=h[tata];
            h[tata]=h[i];
            h[i]=aux;
            i=tata;
        }
        else i=1;
    }
}
void downheap(int i)
{
    int son;
    while(i<=k)
    {
        if(lfs(i)<=k)
        {
            son=lfs(i);
            if(son+1<=k&&D[h[son]]>D[h[son+1]])
                son++;
        }
        else return ;
        if(D[h[i]]>D[h[son]])
        {
            poz[h[i]]=son;
            poz[h[son]]=i;
            aux=h[son];
            h[son]=h[i];
            h[i]=aux;
            i=son;
        }
        else return ;
    }
}
int main()
{
    int m,i,a,b,c,pas;
    node p;
    fscanf(in,"%d %d",&n,&m);
    for(i=1;i<=n;++i)
    {
        fscanf(in,"%d %d %d",&a,&b,&c);
        p.nr=b;
        p.val=c;
        V[a].push_back(p);
    }
    int num=n-1;
    for(i=2;i<=n;++i)
    {
        D[i]=inf;
        poz[i]=-1;
    }
    k=1;
    h[k]=1;
    D[1]=0;
    poz[1]=1;
    while(k)
    {
        pas=h[1];
        h[1]=h[k--];
        poz[h[1]]=1;
        downheap(1);
        for(i=0;i<(int)V[pas].size();++i)
        {
            p=V[pas][i];
            if(D[p.nr]>D[pas]+p.val)
            {
                D[p.nr]=D[pas]+p.val;
                if(poz[p.nr]!=-1)
                    upheap(poz[p.nr]);
                else
                {
                    h[++k]=p.nr;
                    poz[p.nr]=k;
                    upheap(k);
                }
            }
        }
    }
    for(i=2;i<=n;++i)
        fprintf(out,"%d ",D[i]);
    return 0;
}