#include <stdio.h>
#include <vector>
#include <string.h>
#define maxl 50001
#define inf 1<<29
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;
char f[20];
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    scanf("%d %d\n",&n,&m);
    for (i=1; i<=m; ++i)
    {
        fgets(f,18,stdin);
        p=0;q=0;k=0;x=0;
        while (f[x]!=' ') {p=p*10+f[x]-48;++x;}++x;
        while (f[x]!=' ') {q=q*10+f[x]-48;++x;}++x;
        while (f[x]!='\n') {k=k*10+f[x]-48;++x;}
                           
        a[p].push_back(q);
        cost[p].push_back(k);
    	if (i<=n)
	    {
            dist[i]=inf;heap[i]=i;poz[i]=i;
        }
    }

    k=n;
    
    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>>1>0)
                {
                    int aa=x>>1;  
                    if (dist[heap[aa]]>dist[heap[x]])
                    {
                        t=poz[heap[x]];poz[heap[x]]=poz[heap[aa]];poz[heap[aa]]=t;
                        t=heap[aa];heap[aa]=heap[x];heap[x]=t;
                        x>>=1;
                    }
                    else break;
                }
            }

        //scoaterea elementului 1 din heap

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

        x=1;
        while (x<<1<=k)
        {
           p=x<<1;q=p;
           if (q+1<=k) q++;
           if (dist[heap[x]]>dist[heap[p]] || dist[heap[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)
        printf("%d ",dist[i]==inf?0:dist[i]);

    printf("\n");
    
    return 0;
}