#include <stdio.h>
#include <vector>
#define MAXN 50005
#define MAXH 100000
#define INF 1000000000
using namespace std;


struct nod
{
	int y;
	int c;
};

vector<nod> g[MAXN];
nod aux;
int d[MAXN];
bool viz[MAXN];

class Heap
{
public:
	int size;
	nod h[MAXH]; 
	Heap();
	void makeHeap();
	nod getTop();
	void deleteMin();
	void heapSort();
	void heapify(int key);
	void insertElement(nod key);
};

Heap::Heap()
{
	size = 0;
}

void swap(nod &x,nod &y)
{
	nod temp = x;
	x = y;
	y = temp;
}

void Heap::heapify(int key)
{
	while ((h[key].c>h[2*key].c || h[key].c>h[2*key+1].c) && 2*key<=size)
	{
		if (2*key+1>size && h[2*key].c<h[key].c)
		{
			swap(h[key],h[2*key]);
			key = 2*key;
		}
		else if (2*key+1>size)
		{
			return;
		}
		else if (h[2*key].c<h[2*key+1].c)
		{
			swap(h[key],h[2*key]);
			key = 2*key;
		}
		else
		{
			swap(h[key],h[2*key+1]);
			key = 2*key + 1;
		}
	}
}

void Heap::insertElement(nod key)
{
	size++;
	h[size] = key;
	int k = size;
	while (h[k/2].c > h[k].c && k>1)
	{
		swap(h[k/2],h[k]);
		k/=2;
	}
}

nod Heap::getTop()
{
	return h[1];
}

void Heap::deleteMin()
{
	swap(h[1],h[size]);
	size--;
	heapify(1);
}

void Heap::makeHeap()
{
	int i;
	for (i=size/2;i>=1;i--)
	{
		heapify(i);
	}
}

void Heap::heapSort()
{
	int i,sz = size;
	for (i=1;i<=sz;i++)
	{
		deleteMin();
	}
}

int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);

	int n,m,x,y,c,i;
	Heap a;

	scanf("%d%d",&n,&m);

	for (i=0;i<m;i++)
	{
		scanf("%d%d%d",&x,&y,&c);
		aux.y = y;
		aux.c = c;
		g[x].push_back(aux);
	}
	aux.c = 0;
	aux.y = 1;
	a.insertElement(aux);
	d[1] = 0;
	viz[1] = true;
	for (i=2;i<=n;i++)
	{
		d[i] = INF;  
	}
	while (a.size>0)
	{
		int v  = a.getTop().y;
		a.deleteMin();

		for (i=0;i<g[v].size();i++)
		{
			if (g[v][i].c + d[v] < d[g[v][i].y])
			{
				aux.c = g[v][i].c + d[v];
				aux.y = g[v][i].y;
				a.insertElement(aux);
				d[g[v][i].y] = g[v][i].c + d[v];
			}
		}

	}
	for (i=2;i<=n;i++)
	{
		if (d[i] == INF)
		{
			printf("0 ");
		}
		else
		{
			printf("%d ",d[i]);  
		}
	}
	return 0;
}