#include <iostream>
#include <fstream>
#include <vector>
#include <set>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

class edge
{
public:
	int cost;
	int nod;
};

set<pair<int,int> > coada;
vector<int> dis;
vector<vector<edge> > graph;
int n,m;
void dij(int start)
{
	int i;
	dis[start]=0;
	int a,drum;
	coada.insert(make_pair(0,start));
	while(coada.size()>0)
	{
		drum=(*coada.begin()).first;
		a=(*coada.begin()).second;
		coada.erase(coada.begin());
		for(i=0;i<graph[a].size();i++)
		{
			if(dis[graph[a][i].nod]>drum+graph[a][i].cost)
			{
				dis[graph[a][i].nod]=drum+graph[a][i].cost;
				coada.insert(make_pair(drum+graph[a][i].cost,graph[a][i].nod));
			}
		}
		
	}
}
int main()
{
	int i,x,y,z;
	edge aux;
	f>>n>>m;
	graph.resize(n+1);
	dis.resize(n+1,100000000);
	for(i=1;i<=m;i++)
	{
		f>>x>>y>>z;
		aux.nod=y;
		aux.cost=z;
		graph[x].push_back(aux);
	}
	dij(1);
	for(i=2;i<=n;i++)
	if(dis[i]!=100000000)
		   g<<dis[i]<<" ";
	else g<<0<<" ";}