#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
#define NMAX 50005
#define INF 1<<25
int N, M;
struct Punct { int c; int urm; } nod;
vector<Punct> matrice[NMAX];
vector<int> d(NMAX, INF);
bool viz[NMAX];
short start = 1;
void dijkstra() 
{   int x=0;
	d[start] = 0;
	queue <int> Q;
	Q.push(start);
	viz[start] =1;
	while(!Q.empty())
	{   x=Q.front();
		Q.pop();
		viz[x] =0;
		vector<Punct> :: iterator it;
		for(it = matrice[x].begin(); it != matrice[x].end(); ++it)
		  if(d[x] + it->c < d[it->urm]) 
			    {
				d[it->urm] = d[x] + it->c;
				if(!viz[it->urm]) Q.push(it->urm);
			     }
	}
}
void citire() 
{   f>>N>>M;
	int x;
	for(int i=1; i<=M; i++) {
		f>>x>>nod.urm>>nod.c;
		matrice[x].push_back(nod);
	}
	f.close();
}
int main() 
{   citire();
	dijkstra();
	for(int i=2; i<=N; i++)
		if(d[i] == INF) g<<"0 ";	
		else g<<d[i]<<' ';
	g.close();
}