#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 N, M;
int A, B, C;
muchie aux;
int d[Nmax], h[Nmax], p[Nmax];
int nh;

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 afisare () { for(int i = 1; i <= N; i ++) for(int j = 0; j < v[i].size(); j ++) g << v[i][j].y << ' ' << v[i][j].cost << '\n'; }

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 schimba(int x, int y)
{
	int aux;
	aux=h[x];
	h[x]=h[y];
	h[y]=aux;
	
	p[h[x]]=x;
	p[h[y]]=y;
}
void urca(int x)
{
	if(x > 1 && d[h[x]] < d[h[tata(x)]])
	{
		schimba(tata(x), x);
		urca(tata(x));
	}
}

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

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

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 = v[x][i].y;
			int cost = v[x][i].cost;
			
			if(d[x] + cost < d[y])
			{
				d[y] = d[x] + cost;
				if(p[y] == 0)
					adauga(y);
				else
					urca(p[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();
	dijkstra(1);
	afisare();
	//g << '\n' << '\n';
	//for(int i = 1; i <= N; i ++)
		//g << p[h[i]] << ' ';
	return 0;
}