#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

#define N_MAX 50005
typedef pair <int,int> p;
vector <p> a[N_MAX];
vector <p> ::iterator it;
int n,m,i,j,x,y,z;

int cost[N_MAX];
bool ut[N_MAX];

int heap[N_MAX],poz[N_MAX];
int dimHeap;

void upHeap(int x)
{
	while(x>1&&cost[ heap[x>>1] ]>cost[ heap[x] ])
	{
		swap(poz[ heap[x>>1] ],poz[ heap[x] ]);
		swap(heap[x>>1],heap[x]);
		x=x>>1;
	}
}
int st,dr,minim;
void downHeap(int x)
{
	st=x<<1;
	dr=(x<<1)+1;
	minim=x;

	if(st<=dimHeap&&cost[ heap[st] ]<cost[ heap[minim] ])
		minim=st;

	if(dr<=dimHeap&&cost[ heap[dr] ]<cost[ heap[minim] ])
		minim=dr;

	if(minim!=x)
	{
		swap(poz[ heap[x] ],poz[ heap[minim] ]);
		swap(heap[x],heap[minim]);
		downHeap(minim);
	}
}

void sterge(int x)
{
	swap(poz[ heap[x] ],poz[ heap[dimHeap] ]);
	swap(heap[x],heap[dimHeap]);
	
	dimHeap--;

	if(cost[ heap[x>>1] ]>cost[ heap[x] ])
		upHeap(x);
	else
		downHeap(x);
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);

	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		a[x].push_back(p(y,z));
	}

	for(i=1;i<=n;i++)
		cost[i]=(1<<30);

	heap[++dimHeap]=1;
	poz[1]=dimHeap;
	ut[1]=1;	cost[1]=0;

	while(dimHeap)
	{
		int nod=heap[1];
		sterge(poz[nod]);	ut[nod]=0;

		for(it=a[nod].begin();it!=a[nod].end();it++)
		{
			if(cost[nod]+it->second<cost[it->first])
			{
				cost[it->first]=cost[nod]+it->second;
				if(ut[it->first])
					sterge(poz[it->first]);

				heap[++dimHeap]=it->first;
				poz[it->first]=dimHeap;
				upHeap(dimHeap);
				
				ut[it->first]=1;
			}
		}
	}

	for(i=2;i<=n;i++)
	{
		if(cost[i]==(1<<30))
			cost[i]=0;
		printf("%d ",cost[i]);
	}
	return 0;
}