#include <stdio.h>
#include <vector>
#define maxl 50010
#define inf 2147000000
using namespace std;

vector <int> a[maxl];
vector <int> cost[maxl];
int heap[maxl],poz[maxl],dist[maxl];
int i,k,p,q,n,m,x,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,&k);
        a[p].push_back(q);
        cost[p].push_back(k);
    }

    k=n;dist[1]=0;
    for (i=1; i<=n; i++)
    {
        dist[i]=inf;
        heap[i]=i;
        poz[i]=i;
    }
    dist[1]=0;
    while (k>0)
    {
        x=inf;
        p=a[heap[1]].size();
        for (i=0; i<=p-1; i++)
            if (dist[heap[1]]+cost[heap[1]][i]<dist[a[heap[1]][i]])
            {
                dist[a[heap[1]][i]]=dist[heap[1]]+cost[heap[1]][i];
                if (dist[heap[1]]+cost[heap[1]][i]<x)
                {
                    q=a[heap[1]][i];
                    x=dist[heap[1]]+cost[heap[1]][i];
                }
            }

        //scoaterea elementului q din heap
        heap[1]=heap[q];poz[q]=1;
        heap[q]=heap[k];poz[k]=q;
        poz[1]=k;
        k--;

        x=q;
        while (x*2<=k)
        {
           p=2*x;q=2*x;
           if (q+1<=k) q++;
           if (dist[x]>dist[p] || dist[x]>dist[q])
           {
                if (dist[p]>=dist[q])
                {
                   t=dist[p];dist[p]=dist[x];dist[x]=t;
                   t=heap[p];heap[p]=heap[x];heap[x]=t;
                   t=poz[p];poz[p]=poz[x];poz[x]=t;
                   x=p;
                }
                else {
                       t=dist[q];dist[q]=dist[x];dist[x]=t;
                       t=heap[q];heap[q]=heap[x];heap[x]=t;
                       t=poz[q];poz[q]=poz[x];poz[x]=t;
                       x=q;
                     }
           }
           else break;
        }
    }

    for (i=2; i<=n; i++)
        printf("%d ",dist[i]);
    printf("\n");
    
    return 0;
}