#include<fstream>
#include<vector>
using namespace std;
const char* INFILE="dijkstra.in";
const char* OUTFILE="dijkstra.out";
const int MAXN=50010;
const int INF=1<<30;

int n,m,heap_size;
int d[MAXN],h[MAXN],poz[MAXN];;
struct edge{int dest,cost;};
vector<edge> adj[MAXN];


/* READ AND WRITE */
void read()
{
	edge aux;
	int i,u,v,w;
	ifstream fin(INFILE);
	fin>>n>>m;
	for (i=1; i<=m; ++i)
	{
		fin>>u>>v>>w;
		aux.dest=v;
		aux.cost=w;
		adj[u].push_back(aux);
	}

	fin.close();
}
void write()
{
	ofstream fout(OUTFILE);
	for (int i=2; i<=n; ++i)
	{
		if (d[i]==INF)
			fout<<"0 ";
		else
			fout<<d[i]<<' ';
	}
	fout<<'\n';
	fout.close();
}
/* HEAP OPERATIONS */
int parent(int i){return (i>>1);}
int left(int i){return (i<<1);}
int right(int i){return ((i<<1)+1);}
void up_heap(int i)
{
	int son,father;
	while (i>1)
	{
		son=h[i];
		father=h[parent(i)];
		if (d[son]<d[father])
		{
			swap(h[i],h[parent(i)]);
			swap(poz[son],poz[father]);
			i>>=1;
		}
		else
			break;
	}
}
void down_heap(int i)
{
	int l=left(i),r=right(i),smallest=i;
	if (l<=heap_size && d[h[l]]<d[h[smallest]])
		smallest=l;
	if (r<=heap_size && d[h[r]]<d[h[smallest]])
		smallest=r;
	if (smallest!=i)
	{
		int father=h[i],son=h[smallest];
		swap(h[i],h[smallest]);
		swap(poz[son],poz[father]);
		down_heap(smallest);
	}
}

int extract_min()
{
	int top=h[1],bottom=h[heap_size];

	swap(poz[top],poz[bottom]);
	swap(h[1],h[heap_size]);

	poz[h[heap_size]]=-1;
	h[heap_size--]=0;
	down_heap(1);
	return top;
}

/* Dijkstra's Algorithm */
void relax(int u,int v,int w)
{
	if (d[v]>d[u]+w)
	{
		d[v]=d[u]+w;
		up_heap(poz[v]);
	}
}
void dijkstra()
{
	/*Initialization */
	int i,u;
	heap_size=n;
	for (i=1; i<=n; ++i)
	{
		poz[i]=i;
		h[i]=i;
		d[i]=INF;
	}
	d[1]=0;
	/*Relaxing*/
	while (heap_size)
	{
		u=extract_min();
		if (d[u]==INF)
			break;
		for (vector<edge>::iterator i=adj[u].begin(); i!=adj[u].end(); ++i)
		{
			relax(u,(*i).dest,(*i).cost);
		}
	}
}
/* MAIN FUNCTION */
int main()
{
	read();
	dijkstra();
	write();
	return 0;
}