#include<fstream>
#include<vector>
#include<iostream>
#define NMAX 50001
#define INF 50000005
#define pb push_back

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

struct relatie
{
	int nod, cost;
};

vector<relatie> a[NMAX];
int viz[NMAX], n, d[NMAX];

void citeste()
{
	int i, m, x, y, c;
	relatie r;
	f>>n>>m;
	for (i=1; i<=m; ++i)
	{
		f>>x>>y>>c;
		r.nod=y;r.cost=c;
		a[x].pb(r);
	}
	for (i=1; i<=n; ++i) d[i]=INF;
	for (i=0; i<a[1].size(); ++i)
		d[a[1][i].nod]=a[1][i].cost;
}

void verifica()
{
	int i, j;
	for (i=1; i<=n; ++i)
	{
		for (j=0; j<a[i].size(); ++j) cout<<a[i][j].nod<<" "<<a[i][j].cost<<"---";
		cout<<"\n";
	}
}

void solve()
{
	int min, imin, i, lg;
	relatie z;
	viz[1]=1; imin=1;
	while (imin)
	{
		imin=0;min=INF;
		for (i=2; i<=n; ++i)
			if (min>d[i] && viz[i]==0) { min=d[i];imin=i;}
		if (imin>0)
		{
			viz[imin]=1;
			lg=a[imin].size();
			for (i=0; i<lg; ++i)
			{
				z=a[imin][i];
				if (d[z.nod]>d[imin]+z.cost) d[z.nod]=d[imin]+z.cost;
			}
		}
	}
}

void scrie()
{
	int i;
	for (i=2; i<=n; ++i)
		if (d[i]!=INF) g<<d[i]<<" ";
			else g<<"0 ";
}
	
int main()
{
	citeste();
	//verifica();
	solve();
	scrie();
	f.close();
	g.close();
	return 0;
}