#include<fstream>
#include<queue>
#include<vector>
#define N 50100
#define inf (1<<30)
#include<cstring>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
pair<int,int> nod;
priority_queue<pair<int,int> > pq;
vector<pair<int,int> > v[N];
using namespace std;
int n,m,i,D[N],x,viz[N],y,z;
int main ()
{
	f>>n>>m;
	for(i=1;i<=m;++i)
	{
		f>>x>>y>>z;
		v[x].push_back(make_pair(y,z));
	}
	for(i=1;i<=n;++i)
	D[i]=inf;
	D[1]=0;
	pq.push(make_pair(0,1));
	while(!pq.empty())
	{
		nod=pq.top();
		pq.pop();
		if(viz[nod.second])
			continue;
        x=nod.second;
		viz[x]=1;
		for(int i=0;i<v[x].size();++i)
		{
			if(v[x][i].second+D[x]<D[v[x][i].first])
			{
				D[v[x][i].first]=v[x][i].second+D[x];
				pq.push(make_pair(-D[v[x][i].first],v[x][i].first));
			}
		}
	}
	for(i=2;i<=n;++i)
		g<<(D[i]==inf?0:D[i])<<" ";
	return 0;
}