#include<fstream>
#include<vector>
using namespace std;

#define inf 0x3f3f3f3f
#define nmax 50003
#define pb push_back
#define mp make_pair

vector <pair <int, int> > lista[nmax];
int cost[nmax],v[nmax],pozh[nmax],H[nmax],dimh,n,m;

void urca(int nod)
{
	if(nod==1) return;
	
	int tata=nod/2;
	
	if(cost[H[nod]]>=cost[H[tata]]) return ;
	
	swap(H[nod], H[tata]);
	swap(pozh[H[nod]],pozh[H[tata]]);
	
	urca(pozh[H[tata]]);
}

void coboara(int nod)
{
	int fiu1=nod*2;
	int fiu2=nod*2+1;
	int nodmin=nod;
	
	if(cost[H[fiu1]]<cost[H[nodmin]] && fiu1<=dimh)
		nodmin=fiu1;
	if(cost[H[fiu2]]<cost[H[nodmin]] && fiu2<=dimh)
		nodmin=fiu2;
	
	if(nodmin==nod) return ;
	
	swap(H[nod],H[nodmin]);
	swap(pozh[H[nod]], pozh[H[nodmin]]);
	coboara(pozh[H[nodmin]]);
}
	
	



void sterge()
{
	swap(H[1],H[dimh]);
	swap(pozh[H[1]], pozh[H[dimh]]);
	
	dimh--;
	
	coboara(pozh[H[1]]);
}





void resolve()
{
	while(dimh!=0)
	{
		int nod_min=H[1];
		
		for(unsigned int i=0;i<lista[nod_min].size();i++)
		{
			int nod= lista[nod_min][i].first;
			
			if(v[nod]==1) continue;
			
			int cost1=lista[nod_min][i].second;
			
			int cost_tot=cost1+cost[nod_min];
			if(cost_tot<cost[nod])
			{
				cost[nod]=cost_tot;
				urca(pozh[nod]);
			}
		}
		sterge();
		v[nod_min]=1;
		
	}
}
	
int main()
{
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	
	f>>n>>m;
	cost[1]=0;
	for(int i=1;i<=n;i++)
	{
		if(i>1) cost[i]=inf;
		H[++dimh]=i;
		pozh[i]=dimh;
		urca(pozh[i]);
	}
	
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		
		f>>a>>b>>c;
		
		lista[a].pb(mp(b,c));
	}
	
		resolve();
	for(int i=2;i<=n;i++)
	{
		if(cost[i]==inf)
			g<<"0 ";
		else
		g<<cost[i]<<" ";
	}
}