#include <fstream>
using namespace std;

const int N=50003,M=250003,inf=1<<30;
struct arc{int x,y,c;} a[M];
int v[M],dist[M],s[N],n,m;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

inline bool comp(arc a,arc b)
{
	return a.x<b.x;
}

inline void sch(int &a,int &b)
{
	int c=a;a=b;b=c;
}

inline bool cmp(int a,int b)
{
	return dist[a]<dist[b];
}

inline void up(int x)
{
	if (x>1 && cmp(v[x],v[x/2]))
	{
		sch(v[x],v[x/2]);
		up(x/2);
	}
}

inline void down(int x)
{
	int m=x;
	if (2*x<=v[0] && cmp(v[2*x],v[x]))
		m=2*x;
	if (2*x<v[0] && cmp(v[2*x+1],v[x]))
		m=2*x+1;
	if (m!=x)
	{
		sch(v[x],v[m]);
		down(m);
	}
}

inline int del()
{
	int q=v[1];
	v[1]=v[v[0]--];
	down(1);
	return q;
}

inline void add(int x)
{
	v[++v[0]]=x;
	up(v[0]);
}

void dijkstra(int x)
{
	int i,y,c;
	dist[x]=0;
	add(x);
	while (v[0])
	{
		x=del();
		for (i=s[x];i<s[x+1];i++)
		{
			y=a[i].y;c=a[i].c;
			if (dist[y]>dist[x]+c)
			{
				dist[y]=dist[x]+c;
				add(y);
			}
		}
	}
}

int main()
{
	int i,j;
	in>>n>>m;
	for (i=1;i<=m;i++)
		in>>a[i].x>>a[i].y>>a[i].c;
	for (i=1;i<=n;i++)
		dist[i]=inf;
	sort(a+1,a+m+1,comp);
	for (i=j=1,s[n+1]=m+1;i<=n;s[i]=j,i++)
		for (;a[j].x<i && j<=m;j++);
	dijkstra(1);
	for (i=2;i<=n;i++)
		if (dist[i]==inf)
			out<<"0 ";
		else
			out<<dist[i]<<" ";
	out<<"\n";
	return 0;
}