#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define inf 99999999
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n,m;
const int N=1e5;
typedef pair <int,int> pereche;
priority_queue<pereche,vector<pereche>,greater<pereche>> varfuri;
vector <pair<int,int>> graf[N+1];
vector <int> dist,multime,precedent;
void initializare(int s)
{
	for(int i=1; i<=n; i++)
		dist[i]=inf;
	dist[s]=0;
}


void relax(int i,int j,int w)
{
	if(dist[j]>dist[i]+w)
	{
		dist[j]=dist[i]+w;
		precedent[j]=i;
		varfuri.push(make_pair(dist[j],j));
	}
}


void Dijkstra(int s)
{
	int j,w,u;
	initializare(s);
	varfuri.push(make_pair(0,s));
	while(!varfuri.empty())
	{
		u=varfuri.top().second;
		varfuri.pop();
		multime.push_back(u);
		for(auto x:graf[u])
		{
			j=x.first;
			w=x.second;
			relax(u,j,w);
		}
	}
}


int main()
{
	int x,y,w,s;
	f>>n>>m;
	for(int i=1; i<=m; i++)
	{
		f>>x>>y>>w;
		graf[x].push_back(make_pair(y,w));
	}
	s=1;
	dist.resize(n+1);
	multime.resize(n+1);
	precedent.resize(n+1);
	Dijkstra(s);
	for(int i=2; i<=n; i++)
		if(dist[i]==inf)
			g<<"0"<<" ";
		else
			g<<dist[i]<<" ";
	f.close();
	g.close();
	return 0;
}