#include <stdio.h>   
#include <vector>   
#include <algorithm>   
#define inf 0x3f3f3f3f   
using namespace std;   
  
int n,m,x,y,c,b[50001],h[65600],z,p,q,d[50001]; 
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;   
        }   
    }   
    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]];    
                while (p>1)   
                {   
                    if (b[h[p]]<b[h[p>>1]])   
                    {    
                        swap(h[p],h[p>>1]);   
                        swap(d[h[p]],d[h[p>>1]]);   
                        p=p>>1;  
						continue;
                    }   
					break;
                }   
            }   
        d[h[1]]=z;   
        h[1]=h[z--];   
        p=1;   
        while (1)   
        {   
            y=0;   
            if (z>=p*2+1 && b[h[p*2+1]]<b[h[p*2]]) y=1;   
            if (z>=p*2+y && b[h[p]]>b[h[p*2+y]])   
            {   
                q=1;   
                swap(h[p],h[p*2+y]);   
                swap(d[h[p]],d[h[p*2+y]]);   
                p=p*2+y;   
				continue;
            }   
			break;
        }   
    }   
    for (i=2; i<=n; ++i)   
    {   
        //if (b[i]==inf) printf("0 ");
		printf("%d ",b[i]==inf?0:b[i]);   
    }   
    return 0;   
}