#include <fstream>
#include <cstdlib>
#include <climits>

#define I_F "travel.in"
#define O_F "travel.out"
#define MAXn 100000
#define MAXm 200000*2
#define NIL -1

using namespace std;

struct edges
{
	long x,y;
	int t;
};

struct Heap
{
	long tail;
	long s[MAXn+1];
};

long n,m;
edges e[MAXn];
Heap heap;
long g[MAXn],head[MAXn+1];
long l[MAXn],h[MAXn];
long ans[MAXn];

void Input();
inline bool Compare(edges,edges);
inline void Swap(edges&,edges&);
void Qsort(long,long);
void Get_head();
inline void Heap_Start();
inline long Heap_Min(long,long);
inline void Heap_Swap(long,long);
inline void Heap_Fix(long);
inline void Heap_Delete();
inline void Heap_Insert(long);
void Dijkstra(long);
void Output();

int main()
{
	Input();
	Qsort(0,m*2-1);
	Get_head();
	for (long i=0; i<n; Dijkstra(i++));
	Output();
	return 0;
}

void Input()
{
	ifstream fin(I_F);
	fin>>n>>m;
	for (long i=0; i<m; i++)
	{
		fin>>e[i*2].x>>e[i*2].y>>e[i*2].t;
		e[i*2+1].x=--e[i*2].y,
		e[i*2+1].y=--e[i*2].x;
		e[i*2+1].t=e[i*2].t;
	}
	fin.close();
	
	g[0]=NIL;
	for (long i=1; i<n; ans[i++]=NIL);
}

inline bool Compare(edges a, edges b)
{
	if (a.x<b.x)
		return true;
	if (a.x>b.x)
		return false;
	if (a.t<b.t)
		return true;
	return false;
}

inline void Swap(edges &a, edges &b)
{
	edges t=a;
	a=b;
	b=t;
}

void Qsort(long l, long r)
{
	edges x=e[l+rand()%(r-l+1)];
	long i=l, j=r;
	do
	{
		while (Compare(e[i],x)) i++;
		while (Compare(x,e[j])) j--;
		if (i<=j)
			Swap(e[i++],e[j--]);
	} while (i<j);
	if (i<r) Qsort(i,r);
	if (l<j) Qsort(l,j);
}

void Get_head()
{
	long t=e[0].x;
	head[t]=0;
	for (long i=1; i<m*2; i++)
		if (e[i].x>t)
			head[e[i].x]=head[t+1]=i,
			t=e[i].x;
	head[n]=m*2;
}

inline void Heap_Start()
{
	heap.tail=2;
	heap.s[1]=0;
	h[0]=1;
	l[0]=0;
	for (long i=1; i<n; i++)
		h[i]=l[i]=NIL;
}

inline long Heap_Min(long a, long b)
{
	#define A heap.s[a]
	#define B heap.s[b]
	return ((l[A]<l[B])||(b>=heap.tail))?a:b;
}

inline void Heap_Swap(long a, long b)
{
	#define A heap.s[a]
	#define B heap.s[b]
	h[A]=b;
	h[B]=a;
	long t=A;
	A=B;
	B=t;
}

inline void Heap_Fix(long x)
{
	for (long i=x; (i>1)&&(l[heap.s[i]]<l[heap.s[i/2]]); Heap_Swap(i,i/2), i/=2);
}

inline void Heap_Delete()
{
	h[heap.s[1]]=NIL;
	heap.s[1]=heap.s[--heap.tail];
	h[heap.s[1]]=1;
	for (long i=1, t; i*2<heap.tail; i=t)
		t=Heap_Min(i*2,i*2+1),
		Heap_Swap(i,t);
}

inline void Heap_Insert(long x)
{
	#define TAIL heap.tail
	heap.s[TAIL]=x;
	h[x]=TAIL;
	Heap_Fix(TAIL++);
}

void Dijkstra(long x)
{
	for (Heap_Start(); heap.tail>0; Heap_Delete())
		#define NOW heap.s[1]
		#define STEP e[i].y
		if ((NOW==x)&&(x>0))
		{
			ans[x]=l[x];
			break;
		}
		else
			for (long i=head[NOW]; i<head[NOW+1]; i++)
				if ((g[x]!=i)&&((l[STEP]==NIL)||(l[NOW]+e[i].t<l[STEP])))
				{
					l[e[i].y]=l[NOW]+e[i].t;
					if (x==0)
						g[STEP]=i;
					if (h[STEP]==NIL)
						Heap_Insert(STEP);
					else
						Heap_Fix(h[STEP]);
				}
}

void Output()
{
	ofstream fout(O_F);
	for (long i=1; i<n; fout<<ans[i]<<'\n', i++);
	fout.close();
}