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

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


int n,m,cost[nmax],dimh=0,h[nmax],pozh[nmax];
vector <pair <int , int> > lista[nmax];
bool v[nmax];
ofstream g("dijkstra.out");






void push(int pct)
{
	int tata=pct/2;
	if(pct==1) return ;
	if(cost[h[pct]]>=cost[h[tata]]) return ;
	swap(h[pct],h[tata]);
	swap(pozh[h[pct]],pozh[h[tata]]);
	push(pozh[h[tata]]);
}


void pop(int pct)
{
	int f1=pct*2;
	int f2=pct*2+1;
	int pctmin=pct;
	
	if(cost[h[f1]]<cost[h[pctmin]] && f1<=dimh)
		pctmin=f1;
	if(cost[h[f2]]<cost[h[pctmin]] && f2<=dimh)
		pctmin=f2;
	
	if(pct==pctmin) return;
	
	swap(h[pct],h[pctmin]);
	swap(pozh[h[pct]],pozh[h[pctmin]]);
	pop(pozh[h[pctmin]]);
	
}
	
	



void adaug(int pct)
{
	h[++dimh]=pct;
	pozh[pct]=dimh;
	push(dimh);
}

void sterge(int x)
{
	
	swap(h[x],h[dimh]);
	swap(pozh[h[x]],pozh[h[dimh]]);
	dimh--;
	
	push(pozh[h[x]]);
	pop(pozh[h[x]]);
}



void dijkstra()
{
	
	dimh++;
	h[1]=1;
	pozh[1]=1;
	
	while(dimh!=0)
	{
		int nod_minim=h[1];
		//g<<nod_minim<<"\n";
		for(unsigned int i=0;i<lista[nod_minim].size();i++)
		{
			int nod=lista[nod_minim][i].first;
			if(v[nod]==1) continue;
			int cost1=lista[nod_minim][i].second;
			int cost_tot=cost1+cost[nod_minim];
			if(cost_tot<cost[nod])
			{
				cost[nod]=cost_tot;
				//sterge(pozh[nod]);
				adaug(nod);
			}
		}
		sterge(pozh[nod_minim]);
		v[nod_minim]=1;
	}
}
		



int main()
{
	ifstream f("dijkstra.in");
	
	
	f>>n>>m;
	cost[1]=0;
	for(int i=2;i<=n;i++)
		cost[i]=inf;
	
	for(int i=1;i<=m;i++)
	{
		int a,b,c;
		f>>a>>b>>c;
		lista[a].pb(mp(b,c));
		adaug(i);
	}
	
	dijkstra();
	
	for(int i=2;i<=n;i++)
	{
		if(cost[i]==inf)
		{
			g<<"0 ";
			continue;
		}
		g<<cost[i]<<" ";
	}
	
}