#include<cstdio>
#include<vector>
#include<algorithm>
#define infile "dijkstra.in"
#define outfile "dijkstra.out"
#define n_max 50005
#define INF 1 << 30
#define pb push_back
#define mkp make_pair
#define ls(i) i<<1
#define rs(i) (i<<1) + 1
#define f(i) i>>1
using namespace std;

int n,m;

vector < pair <int, int> > v[n_max];

int h[n_max], d[n_max], poz[n_max];

int N;


int get_min_heap();
void percolate(int);
void sift(int);
void insert(int);

void init()
{
	h[++N] = 1;
	
	poz[1] = 1;
	
	for(int i=2;i<=n;i++)
		d[i] = INF;
}





void citeste()
{
	freopen(infile,"r",stdin);
	
	scanf("%d %d",&n,&m);
	
	int x,y,c;
	
	while(m--)
	{
		scanf("%d %d %d",&x,&y,&c);
		
		v[x].pb(mkp(y,c));
	}
	
	fclose(stdin);
}




void rezolva()
{
	int nodm;
	
	while(N)
	{
		nodm = get_min_heap();
		
		for(unsigned int i=0; i<v[nodm].size(); ++i)
			if(d[v[nodm][i].first] > d[nodm] + v[nodm][i].second)
			{
				d[v[nodm][i].first] = d[nodm] + v[nodm][i].second;
				
				if(poz[v[nodm][i].first])
					percolate(poz[v[nodm][i].first]);
				else
					insert(v[nodm][i].first);
			}				
	}
}



void insert(int nod)
{
	h[++N] = nod;
	
	poz[nod] = N;
	
	percolate(poz[nod]);
}



int get_min_heap()
{
	int minim = h[1];
	
	h[1] = h[N--];
	poz[ h[1] ] = 1;
	
	sift(1);
	
	return minim;
}



void sift(int k)
{
	int son = k, l = ls(k), r = rs(k);
	
	if(l<=N && d[h[l]] < d[h[son]])
		son = l;
	if(r<=N && d[h[r]] < d[h[son]])
		son = r;
	
	if(son!=k)
	{
		swap(poz[h[son]], poz[h[k]]);
		swap(h[son],h[k]);
		
		sift(son);
	}
}



void percolate(int k)
{
	while(k > 1 && d[h[k]] < d[h[f(k)]])
	{
		swap(poz[h[k]], poz[h[f(k)]]);
		swap(h[k], h[f(k)]);
		
		k = f(k);
	}
}



void afiseaza()
{
	freopen(outfile,"w",stdout);
	
	for(int i=2;i<=n;i++)
		printf("%d ",d[i] == INF ? 0 : d[i]);

	fclose(stdout);
}




int main()
{
	citeste();
	init();
	rezolva();
	afiseaza();
	
	return 0;
}