/*
    Keep It Simple!
*/
  
#include<stdio.h>
#include<list>
  
#define max 50001

using namespace std;
  
int n,m;
long long L[max];
bool viz[max];
int H[max],P[max],k;
  
list< pair<int,int> > G[50001];
  
int min()
{
    int x = 0;
    for(int i=2;i<=n;i++)
        if(!viz[i])
         if(L[i] < L[x]) x = i;
    return x==0 ? 1:x;
}
void swap(int v[],int a,int b)
{
	int aux = v[a];
	v[a] = v[b];
	v[b] = aux;
}

void Update(int x)
{
	int sw = 0;
	while(x/2>0 && !sw)
	{
		sw=1;
		if(L[H[x/2]]>L[H[x]])
		{
			sw=0;
			swap(P,H[x/2],H[x]);
			swap(H,x/2,x);
		}
	}
}
void GoDown(int x)
{
	int sw = 0;
	while( (2*x+1)<=k || (2*x)<=k )
	{
		if ( sw ) break;
		sw = 1;
		if(L[H[2*x+1]] < L[H[x]]){ x = 2*x+1; sw = 0;}
		else if ( L[H[2*x]] < L[H[x]] ) { x = 2*x; sw = 0; }
		
		if( !sw )
		{
		  swap(P,H[x],H[x/2]);
		  swap(H,x,x/2);
		}
	}
}
void Delete(int x)
{
	int aux = L[x];
	L[x] = -1;
	Update(P[x]);
	H[1] = H[k--];
	P[H[1]]=1;
	GoDown(1);
	L[x] = aux;
}
void Dijkstra()
{
    int i=1;
    L[1] = 0;
        while(!viz[i])
        {
            for(list< pair<int,int> >::iterator it = G[i].begin(); it!=G[i].end(); it++)
                if(!viz[it->first])
                 if(L[it->first] > ( L[i] + it->second) )
				 {
                     L[it->first] = L[i] + it->second;
					 Update(P[it->first]);
				 }
            viz[i] = 1;
			Delete(i);
            i = H[1];
        }
}
  
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
      
    scanf("%d %d",&n,&m);
    int x,y,c;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        G[x].push_back( make_pair(y,c) );
    }
		k=n;
    for(int i=0;i<=n;i++) { L[i] = 2000000000; H[i] = i; P[i] = i; }
    Dijkstra();
	for(int i=0;i<=n;i++) if ( L[i] == 2000000000 ) L[i] = 0;
    for(int i=2;i<=n;i++)
        printf("%lld ",L[i]);
}