#include<fstream>
#include<vector>
#include<utility>
#include<set>
#define NMAX 50010
#define INF 250000999
#define f first
#define s second

using namespace std;

ifstream f("djk.in");
ofstream g("djk.out");

vector<pair<int, int> > a[NMAX];
multiset<pair<int, int> > d;
pair<int, int> pr;
int n, m, mn[NMAX], nr[NMAX];
bool vz[NMAX];

void Citeste()
{
	int i, x, y, c;
	
	f>>n>>m;
	for (i=1; i<=m; ++i)
	{
		f>>x>>y>>c;
		a[x].push_back(make_pair(y, c));
		++nr[x];
	}
}

void Initializeaza()
{
	int i;
	for (i=1; i<=n; ++i) mn[i]=INF;
	for (i=0; i<nr[1]; ++i)
	{
		pr=make_pair(a[1][i].s, a[1][i].f);
		mn[a[1][i].f]=a[1][i].s;
		d.insert(pr);
	}
	vz[1]=1;
}

void Solve()
{
	int i, number=n-1, sum;
	
	while (number && !d.empty())
	{
		pr=*(d.begin()); d.erase(d.begin());
		if (!vz[pr.s])
		{
			--number; vz[pr.s]=1;
			for (i=0; i<nr[pr.s]; ++i)
			{
				sum=pr.f+a[pr.s][i].s;
				if (sum<mn[a[pr.s][i].f])
					if (!vz[a[pr.s][i].f]) d.insert(make_pair(sum, a[pr.s][i].f)), mn[a[pr.s][i].f]=sum;
			}
		}
	}
	for (i=2; i<=n; ++i) 
		if (mn[i]!=INF) g<<mn[i]<<" ";
		else g<<"0 ";
	g<<"\n";
}

int main()
{
	Citeste();
	
	Initializeaza();
	
	Solve();
	
	f.close();
	g.close();
	return 0;
}