#include <fstream>
#include <vector>
using namespace std;

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

const int Nmax = 50001;
const int INF = (1 << 30)-1;

struct muchie { int y; int cost; };
vector <muchie> v[Nmax];
int h[Nmax], d[Nmax], poz[Nmax];
int N, M;
muchie aux;
int A, B, C; 
int nh;

inline int tata(int nod) { return nod/2; }
inline int fiu_stanga(int nod) { return nod*2; }
inline int fiu_dreapta(int nod) { return nod*2+1; }

void citire ()
{
	f >> N >> M;
	for(int i = 1; i <= M; i ++) 
	{
		f >> A >> B >> C;
		aux.y = B;
		aux.cost = C;
		v[A].push_back(aux);
	}
}

void vectorul()
{
	for(int i = 1; i <= N; i ++)
	{
		for(size_t j = 0; j < v[i].size(); j ++)
			g << v[i][j].y << ' ' << v[i][j].cost << ' ';
		g << '\n';
	}
}

void schimba(int x, int y)
{
	int aux;
	
	aux=h[x];
	h[x]=h[y];
	h[y]=aux;
	
	poz[h[x]]=x;
	poz[h[y]]=y;
}

void urca(int nh)
{
	if((nh > 1) && d[h[nh]] < d[h[tata(nh)]])
	{
		schimba(tata(nh), nh);
		urca(tata(nh));
	}
}
void coboara(int x)
{
	int bun;
	bun=x;
	if(fiu_stanga(x) <= nh && h[fiu_stanga(x)] < h[bun]) bun=fiu_stanga(x);
	if(fiu_dreapta(x) <= nh && h[fiu_dreapta(x)] < h[bun]) bun=fiu_dreapta(x);
	if(bun != x)
	{
		schimba(x, bun);
		coboara(bun);
	}
}

void adauga(int x)
{
	nh++;
	h[nh]=x;
	poz[h[nh]]=x;
	urca(nh);
}

void sterge(int x)
{
	schimba(1, nh);
	nh--;
	urca(nh);
	coboara(nh);
}

void dijkstra(int x)
{
	for(int i = 1; i <= N; i ++) d[i] = INF; d[x]=0;
	
	nh=0;
	adauga(x);
	
	while(nh != 0)
	{
		x=h[1];
		sterge(1);
		for(size_t i = 0; i < v[x].size(); i ++)
		{
			int y, cost;
			y = v[x][i].y;
			cost = v[x][i].cost;
			
			if(d[x] + cost < d[y])
			{
				d[y] = d[x] + cost;
				if(poz[y] == 0)
					adauga(y);
				else
					urca(poz[y]);
			}
		}
	}	
}
void afisare()
{
    for(int i = 2; i <= N; i ++)
        if(d[i] == INF)
            g << 0 << ' ';
        else
            g << d[i] << ' ';
    g << '\n';
}
int main ()
{
	citire();
	//vectorul();
	dijkstra(1);
	afisare();
	return 0;
}