#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)
    {
        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];
                x=poz[a[heap[1]][i]];
                while (x/2>0)
                {
                    if (dist[heap[x/2]]>dist[heap[x]])
                    {
                        t=poz[heap[x]];poz[heap[x]]=poz[heap[x/2]];poz[heap[x/2]]=t;
                        t=heap[x/2];heap[x/2]=heap[x];heap[x]=t;
                        x/=2;
                    }
                    else break;
                }
            }

        //scoaterea elementului q din heap

        poz[heap[1]]=-1;
        heap[1]=heap[k];
        poz[1]=k;poz[k]=1;
        
        heap[k]=0;
        k--;

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

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