#include<iostream>
#include<fstream>
#include<queue>
#include<vector>
#include<bitset>
using namespace std;
int n,m;
struct pereche{ int n,c;};
vector <pereche> a[50001];
int d[50001];
bitset <50001> apar;
void dijkstra( int nod)
{
	int i,curent;
	queue <int> q;
	q.push(nod);
	apar[nod]=1;
	while (!q.empty())
	{
		nod=q.front();
		q.pop();
		apar[nod]=0;
		for(i=0;i<a[nod].size();i++)
		{
			curent=a[nod][i].n;
			if (d[curent]==0 || d[curent]>d[nod]+a[nod][i].c)
			{
				d[curent]=d[nod]+a[nod][i].c;
				if (apar[curent]==0)
				{
					q.push(curent);
					apar[curent]=1;
				}
			}
		}
	}
}
int main(void)
{
	fstream f,g;
	f.open("dijkstra.in",ios::in);
	g.open("dijkstra.out",ios::out);
	f>>n>>m;
	int i,q;
	pereche z;
	for (i=1;i<=m;i++)
	{
		f>>q>>z.n>>z.c;
		a[q].push_back(z);
	}
	dijkstra(1);// sau defapt bellman-ford :-??
	for (i=2;i<=n;i++)
		g<<d[i]<<" ";
}