#include<iostream>
#include<vector>
#define MAX 50005
#define inf 60000000


using namespace std;

vector<int> szom[MAX],cost[MAX];
int n,m,k=0;
int h[MAX],poz[MAX],d[MAX];

/*
void percolate(int x){
	int temp;
	
	
	while(x/2>=1 && d[h[x/2]]>d[h[x]]){
		temp=h[x];
		h[x]=h[x/2];
		h[x/2]=temp;
		poz[h[x]]=x;
		poz[h[x/2]]=x/2;
		x/=2;
	}
	
	
	
}


void sift(int x){
	int son=x,temp;
	bool jo=true;
	
	while(jo){
		son=x;
		jo=false;
		
		if(2*x<=k && d[h[2*x]]<d[h[x]])son=2*x;
		
		if(2*x+1<=k && d[h[2*x+1]]<d[h[son]])son=2*x+1;
		
		if(son!=x){
			jo=true;
			temp=h[x];
			h[x]=h[son];
			h[son]=temp;
			
			poz[h[son]]=son;
			poz[h[x]]=x;
			
		}
		
		x=son;
	}
	
	
}

*/





void swap(int x, int y)
{
    int t = h[x];
    h[x] = h[y];
    h[y] = t;
}
void percolate(int what)
{
    int tata;
    while ( what > 1 )
    {
        tata = what >> 1;

        if ( d[ h[tata] ] > d[ h[what] ] )
        {
            poz[ h[what] ] = tata;
            poz[ h[tata] ] = what;

            swap(tata, what);

            what = tata;
        }
        else
            what = 1;
    }
}

void sift(int what)
{
    int f;
    while ( what <= k )
    {
        f = what;
        if ( (what<<1) <= k )
        {
            f = what << 1;
            if ( f + 1 <= k )
                if ( d[ h[f + 1] ] < d[ h[f] ] )
                    ++f;
        }
        else
            return;

        if ( d[ h[what] ] > d[ h[f] ] )
        {
            poz[ h[what] ] = f;
            poz[ h[f] ] = what;

            swap(what, f);

            what = f;
        }
        else
            return;
    }
}


void dijk(){
	int min,temp;
	int i;
	
	for(i=1;i<=n;i++){
		poz[i]=-1;
		d[i]=inf;}
	
	k++;
	h[1]=1;poz[1]=1;d[1]=0;
	
	while(k){
		min=h[1];
		
		h[1]=h[k];
		k--;poz[h[1]]=1;
		sift(1);
		
		temp=szom[min].size();
		for(i=0;i<temp;i++){
		
			if(d[min]+cost[min][i]<d[szom[min][i]]){

				d[szom[min][i]]=d[min]+cost[min][i];
				
				if(poz[szom[min][i]]==-1){
					
					k++;
					h[k]=szom[min][i];
					poz[szom[min][i]]=k;
					percolate(k);
					
				}else{
					
					percolate(poz[szom[min][i]]);
				}

			}				
		}
		
		
	}
	
	
}


int main(){
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	int i,temp1,temp2,temp3;
	
	scanf("%d %d",&n,&m);
	
	for(i=1;i<=m;i++){
		scanf("%d %d %d",&temp1,&temp2,&temp3);
		
		szom[temp1].push_back(temp2);
		cost[temp1].push_back(temp3);
		
	}
	
	dijk();
	
	for(i=2;i<=n;i++)
		if(d[i]==inf)printf("0 ");else
		printf("%d ",d[i]);
	
	
return 0;}