#include <fstream>
#include <queue>

using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
const int NMAX=50005,INF=1e9;
int n,m,x,y,cost,bst[NMAX],VIZ[NMAX];
vector <pair<int,int>> V[NMAX];
priority_queue <pair<int,int>> pq; 
void dijkstra()
{
	for(int i=1;i<=n;i++)
		bst[i]=INF;
	pq.push({0,1});
	bst[1]=0;
	while(!pq.empty())
	{
		x=pq.top().second;
		pq.pop();
		if(VIZ[x]) continue;
		VIZ[x]=1;
		for(auto edge: V[x])
		{
			y=edge.first;
			cost=edge.second;
			if(bst[y]>bst[x]+cost)
			{
				bst[y]=bst[x]+cost;
				VIZ[y]=0;
				pq.push({-bst[y],y});
			}
		}
	}
}
int main()
{
	fi>>n>>m;
	for(int i=1;i<=m;i++)
	{
		fi>>x>>y>>cost;
		V[x].push_back({y,cost});
	}
	dijkstra();
	for(int i=2;i<=n;i++)
		if(bst[i]!=INF)
			fo<<bst[i]<<" ";
		else fo<<"0 ";
	fi.close();
	fo.close();
	return 0;
}