#include <fstream>
#include <vector>
#include <queue>
using namespace std;
#define NMAX 50001
#define INF 9876543
int N, M;
struct NodVecin {
	unsigned short int Distanta;
	unsigned int Vecin;
} nod;
vector<NodVecin> Graf[NMAX];
vector<int> dist(NMAX, INF);
bool Vizitat[NMAX];
short NodStart = 1;
void dijkstra() 
{
	int NodCurent = 0;
	dist[NodStart] = 0;
	queue <int> Q;
	Q.push(NodStart);
	Vizitat[NodStart] = true;
	
	while(!Q.empty())
	{   NodCurent = Q.front();
		Q.pop();
		Vizitat[NodCurent] = false;
		vector<NodVecin> :: iterator it;
		for(it = Graf[NodCurent].begin(); it != Graf[NodCurent].end(); ++it)
		  if(dist[NodCurent] + it->Distanta < dist[it->Vecin]) 
			    {
				dist[it->Vecin] = dist[NodCurent] + it->Distanta;
				if(!Vizitat[it->Vecin]) Q.push(it->Vecin);
			     }
	}
}
void citire() 
{   ifstream f("dijkstra.in");
	f>>N>>M;
	int x;
	for(int i=1; i<=M; i++) {
		f>>x>>nod.Vecin>>nod.Distanta;
		Graf[x].push_back(nod);
	}
	f.close();
}
int main() 
{   citire();
	dijkstra();
	ofstream g("dijkstra.out");
	for(int i=2; i<=N; i++)
		if(dist[i] != INF)
			g<<dist[i]<<' ';	
		else g<<0<<' ';
	g.close();
}