#include<cstdio>
#include<vector>
#include<set>
#define beg (*s.begin())
#define mp make_pair
#define pb push_back

using namespace std;

const int N=50001,INF=1000000000,R=31;

int n,m,d[N],len[N];

vector < int > g[N],c[N];

set< pair<int,int> > s;

void ini()
{
	for( int i=2 ; i<=n ; ++i )
		d[i]=INF;
}

void read()
{
	int x,y,z;
	
	char read[R];
	
	fgets(read,R,stdin);
	
	int number=0,i=0;
	
	while( read[i]>='0' &&  read[i]<='9' )
	{
		number= number*10 + read[i]-'0';
		++i;
	}
	n=number;
	number=0;
	++i;
	while( read[i]>='0' &&  read[i]<='9' )
	{
		number= number*10 + read[i]-'0';
		++i;
	}
	m=number;
	
	while(m--)
	{
		fgets(read,R,stdin);
		
		i=0;
		number=0;
		
		while( read[i]>='0' &&  read[i]<='9' )
		{
			number= number*10 + read[i]-'0';
			++i;
		}
		
		x=number;
		++i;
		number=0;
		
		while( read[i]>='0' &&  read[i]<='9' )
		{
			number= number*10 + read[i]-'0';
			++i;
		}
		
		y=number;
		++i;
		number=0;
		
		while( read[i]>='0' &&  read[i]<='9' )
		{
			number= number*10 + read[i]-'0';
			++i;
		}
		
		z=number;
		++i;
		number=0;
		
		++len[x];
		g[x].pb(y);
		c[x].pb(z);
	}
	
	ini();
}

void check( int cost , int nod )
{
	for( int i=0 ; i<len[nod] ; ++i )
		if( d[ g[nod][i] ] > cost + c[nod][i]  )
		{
			d[ g[nod][i] ] = cost + c[nod][i];
			s.insert( mp( d[ g[nod][i] ] , g[nod][i] ) );
		}
}

void parc()
{
	s.insert( mp(0,1) );
	
	int cost,nod;
	
	while( !s.empty() )
	{
		cost=beg.first;
		nod=beg.second;
		s.erase(beg);
		check( cost , nod );
	}
}

void afis()
{
	for( int i=2 ; i<=n ; ++i )
		printf("%d ", ( d[i]==INF ? 0:d[i] ) );
	printf("\n");
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	
	read();
	
	parc();
	
	afis();
	
	return 0;
}