#include <stdio.h>
#include <vector>
using namespace std;

vector <int> a[50010];
vector <int> cost[50010];
int h[50010],fol[50010],nh[50010],dist[50010];
int i,j,k,n,m,p,q,r,t;
int main()
{


    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    scanf("%d %d",&n,&m);

    for (i=1; i<=m; i++)
    {
        scanf("%d %d %d",&p,&q,&r);
        a[p].push_back(q);
        cost[p].push_back(r);
    }

    int sum=1;
    k=1;h[k]=0;nh[k]=1;fol[1]=1;
    while (sum<n)
    {
        q=a[nh[1]].size()-1;
        for (i=0; i<=q; i++)
        if (fol[a[nh[1]][i]]==0)
        {
            fol[a[nh[1]][i]]=1;sum++;
            k++;
            nh[k]=a[nh[1]][i];
            h[k]=h[1]+cost[nh[1]][i];
            dist[a[nh[1]][i]]=h[k];
            j=k;
            while (j>0)
            {
                if (h[j/2]>h[j])
                {
                    p=h[j/2];h[j/2]=h[j];h[j]=p;
                    p=nh[j/2];nh[j/2]=nh[j];nh[j]=p;
                    j/=2;
                }
                else break;
            }
        }
        h[1]=h[k];nh[1]=nh[k];h[k]=0;nh[k]=0;
        k--;j=1;
        if (k>0)
        while (j*2<=k)
        {
            p=2*j;q=2*j;
            if (2*j+1<=k) q++;
            if (h[j]>h[p] || h[j]>h[q])
            {
                if (h[p]<=h[q])
                {
                    t=h[j];h[j]=h[p];h[p]=t;
                    t=nh[j];nh[j]=nh[p];nh[p]=t;
                    j=p;
                }
                else {
                        t=h[j];h[j]=h[q];h[q]=t;
                        t=nh[j];nh[j]=nh[q];nh[q]=t;
                        j=q;
                     }
            }
            else break;
        }
    }
    for (i=2; i<=n; i++) printf("%d ",dist[i]);
    printf("\n");

    return 0;
}