#include <fstream>
#include <queue>
#include <vector>
#define INF 1000000000
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
int N,M;
priority_queue <pair<int, int> > H;
vector <pair<int, int> > V[50001];
vector <pair<int, int> > :: iterator it;
int D[50001];
int S[50001];
int main()
{
	fi>>N>>M;
	for (int i=1;i<=M;i++)
	{
		int sursa,dest,cost;
		fi>>sursa>>dest>>cost;
		V[sursa].push_back(make_pair(cost,dest));
	}
	for (int i=1;i<=N;i++)
	{
		D[i]=INF;
		S[i]=0;
	}
	D[1]=0;
	H.push(make_pair(0,1));
	int i;
	i=1;
	while (1)
	{
		if (H.empty())
			break;
		// se extrage varful heap-ului
		pair <int, int> p;
		int x,y;
		p=H.top();
		H.pop();
		x=p.second;
		if (S[x]==1)
			continue;
		S[x]=1;
		i++;
		if (i==N)
			break;
		D[x]=-p.first;
		// relaxare datorata varfului x
		for (it=V[x].begin();it!=V[x].end();it++)
		{
			y=(*it).second;
			if (S[y]==0)
				if (D[x]+(*it).first<D[y])
				{
					D[y]=D[x]+(*it).first;
					H.push(make_pair(-D[y],y));
				}
		}
	}
	for (int i=2;i<=N;i++)
		if (D[i]==INF)
			fo<<0<<" ";
		else
			fo<<D[i]<<" ";
	fi.close();
	fo.close();
	return 0;
}