#include <stdio.h>   
#include <vector>   
#include <algorithm>   
#define inf 0x3f3f3f3f   
using namespace std;   
  
int n,m,x,y,c,b[50010],h[65610],z,p,q,d[50010]; 
char s[20];
vector <int> a[50000];   
vector <int> cost[50000];   
  
int main()   
{   
    freopen("dijkstra.in","r",stdin);   
    freopen("dijkstra.out","w",stdout);   
    scanf("%d%d\n",&n,&m);   
    int i,j;   
    for (i=1; i<=m; ++i)   
    {   
		fgets(s,20,stdin);
		x=0;y=0;c=0;
		j=0;
		while (s[j]!=' ') x=x*10+s[j++]-48;
		++j;
		while (s[j]!=' ') y=y*10+s[j++]-48;
		++j;
		while (s[j]!='\n') c=c*10+s[j++]-48;
        a[x].push_back(y);   
        cost[x].push_back(c);   
        if (i<=n )   
        {   
            b[i]=inf;   
            h[i]=i;   
            d[i]=i;   
        }   
    }   
    for (i=m; i<=n; ++i) { b[i]=inf;h[i]=i;d[i]=i; }   
    b[1]=0;   
    z=n;   
    for (i=1; i<=n; ++i)   
    {   
        for (j=0; j<a[h[1]].size(); ++j)   
            if (b[h[1]]+cost[h[1]][j]<b[a[h[1]][j]])    
            {   
                b[a[h[1]][j]]=b[h[1]]+cost[h[1]][j];   
                p=d[a[h[1]][j]];   
                q=1;   
                while (q==1 && p>1)   
                {   
                    q=0;   
                    if (b[h[p]]<b[h[p>>1]])   
                    {   
                        q=1;   
                        swap(h[p],h[p>>1]);   
                        swap(d[h[p]],d[h[p>>1]]);   
                        p=p>>1;   
                    }   
                }   
            }   
        d[h[1]]=z;   
        h[1]=h[z--];   
        p=1;   
        q=1;   
        while (q==1)   
        {   
            y=1;   
            if (z>=p*2+1 && b[h[p*2+1]]<b[h[p*2]]) y=2;   
            q=0;   
            if (z>=p*2 && b[h[p]]>b[h[p*2]] && y==1)   
            {   
                q=1;   
                swap(h[p],h[p*2]);   
                swap(d[h[p]],d[h[p*2]]);   
                p=p*2;   
            }   
            if (z>=p*2+1 && b[h[p]]>b[h[p*2+1]] && q==0 && y==2)   
            {   
                q=1;   
                swap(h[p],h[p*2+1]);   
                swap(d[h[p]],d[h[p*2+1]]);   
                p=p*2+1;   
            }   
        }   
    }   
    for (i=2; i<=n; ++i)   
    {   
        if (b[i]==inf) { printf("0 "); continue; }   
        printf("%d ",b[i]);   
    }   
    return 0;   
}