#include<stdlib.h>
#include<fstream>
#include<iostream>
using namespace std;
#define inf 0x3f3f3f3f
#define tata(i) i>>1
#define left(i) i<<1
#define right(i) (i<<1)+1
#define maxn 50001
int d[maxn],t[maxn],v[maxn],p[maxn],n,m,nr;

struct nod
{
	int info;
	int cost;
	nod *ls;
}; 
nod *ad[maxn];


void citire()
{
	ifstream in("dijkstra.in");
	int i,a,b,c;
	nod *temp;
	in>>n>>m;
	for(i=1;i<=m;++i)
	{
		in>>a;
		in>>b;
		in>>c;
		temp=ad[a];
		ad[a]=new nod;
		ad[a]->info=b;
		ad[a]->cost=c;
		ad[a]->ls=temp;
	}
}
inline void swap(int i,int j)
{
	int aux=v[i];
	v[i]=v[j];
	v[j]=aux;
	p[v[i]]=i;
	p[v[j]]=j;
}
inline void heapup(int poz)
{
	if(poz<=1) return;
	if(d[v[tata(poz)]]>d[v[poz]]) swap(poz,tata(poz)),heapup(tata(poz));
}

inline void INSERT(int nod)
{
	v[++nr]=nod;
	p[nod]=nr;	
	heapup(nr);
}

inline void heapdown(int poz)
{
	int m=poz;
	if(left(poz)<=nr)
		if(d[v[left(poz)]]<d[v[poz]]) m=left(poz);
	if(right(poz)<=nr)
		if(d[v[right(poz)]]<d[v[m]]) m=right(poz);
	if(poz!=m) swap(poz,m), heapdown(m);
}
inline int EXTRACT()
{
	swap(1,nr--);
	heapdown(1);
	return v[nr+1];
}

void dijkstra(int x)
{
	int i,nd;
	for(i=1;i<=n;++i) d[i]=inf, t[i]=x;
	nod *tmp=ad[x];
	for(;tmp;tmp=tmp->ls) d[tmp->info]=tmp->cost;
	
	d[x]=0;
	t[x]=0;
	d[0]=-inf;

	for(i=1;i<=n;i++) if(i!=x) INSERT(i);


while(nr)
{
	nd=EXTRACT();

	for(nod *tmp=ad[nd];tmp;tmp=tmp->ls)
		if(d[tmp->info]>d[nd]+tmp->cost)
		{
			d[tmp->info]=d[nd]+tmp->cost;
			heapup(p[tmp->info]);
		}
	
}
}
int main()
{
	int i;
	citire();
	ofstream out("dijkstra.out");
	dijkstra(1);
	for(i=2;i<=n;i++) if(d[i]<inf) out<<d[i]<<" "; else out<<"0 ";
	//cout<<"\nT: "; for(i=1;i<=n;i++) cout<<t[i]<<" ";
	out<<"\n";
	return 0;
}