#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],ind[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);
    }
    for (i=1; i<=n; i++) ind[i]=-1;

    int sum=1;
    k=1;h[k]=0;nh[k]=1;fol[1]=1;
    while (sum<n)
    {
        q=a[nh[1]].size()-1;
        ind[nh[1]]++;i=ind[nh[1]];
        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;
            }
        }
        if (ind[nh[1]]==q)
        {
            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;
}