#include <stdio.h>
#include <vector>
#include <queue>
#define NMAX 50005
#define INF 1<<29
using namespace std;
struct distanta { int nod,c; } t,u;
vector <distanta> v[NMAX];
int d[NMAX],s[NMAX];
int n,m;

class cmp
{
public:
	bool operator() (const distanta &a, const distanta &b)
	{
		return (a.c > b.c);
	}
};

priority_queue < distanta, vector < distanta >, cmp > pq;

void read()
{
	int x;
	
	scanf ("%d%d", &n,&m);
	
	for (int i=1;i<=m;i++)
	{
		scanf ("%d%d%d", &x,&t.nod,&t.c);
		
		v[x].push_back(t);
	}
	
	for (int i=1;i<=n;i++)
		d[i]=INF;
}

void dijkstra(int source)
{
	d[source]=0;
	
	t.nod=source;
	t.c=0;
	
	pq.push(t);
	
	while ( !pq.empty() )
	{
		u=pq.top();		pq.pop();
		
		if (s[u.nod]==1)
			continue;
		
		s[u.nod]=1;
		
		for (int i=0;i<v[u.nod].size();i++)
		{
			if ( d[v[u.nod][i].nod] > d[u.nod] + v[u.nod][i].c )
			{
				d[v[u.nod][i].nod] = d[u.nod] + v[u.nod][i].c;
				
				t.nod=v[u.nod][i].nod;
				t.c = d[v[u.nod][i].nod];
				
				pq.push(t);
			}
		}
	}
}

int main()
{
	freopen ("dijkstra.in", "r", stdin);
	freopen ("dijkstra.out", "w", stdout);
	
	read();
	
	dijkstra(1);
	
	for (int i=2;i<=n;i++)
	{
		if (d[i]==INF)
			d[i]=0;
		
		printf ("%d ", d[i]);
	}
	
	return 0;
}