#include <fstream>
#include <vector>
#define MAXIM 1<<30
using namespace std;

typedef struct {int v,c;} NOD;
NOD Q;

int n,m;
int u=0,p=0;
int a,b,c,i;
int COST[1<<18],C[50001];
vector <NOD> A[1<<16];

void bf()
{
	int i,x,varf,cost;
	p++;
	u++;
	C[p]=1;
	while (p<=u)
	{
		x=C[p];
		p++;
		for (i=0;i<A[x].size();i++)
		{
			varf=A[x][i].v;
			cost=A[x][i].c;
			if (COST[x]+cost>=COST[varf])
				continue;
			C[++u]=varf;
			COST[varf]=COST[x]+cost;
		}
	}
}

int main()
{
	ifstream f("dijkstra.in");
	ofstream g("dijkstra.out");
	f>>n>>m;
	
	for (i=1;i<=m;i++)
	{
		f>>a>>b>>c;
		Q.v=b;
		Q.c=c;
		A[a].push_back(Q);
	}
	for (i=2;i<=n;i++)
		COST[i]=MAXIM;
	bf();
	for (i=2;i<=n;i++)
		if (COST[i]==MAXIM)
			g<<0<<" ";
		else 
			g<<COST[i]<<" ";
	f.close();
	g.close();
	return 0;
}