#include <fstream>
#include <queue>
#include <algorithm>
#define pii pair <int,int>
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define NMAX 50005
using namespace std;
int n,m,best[NMAX];
vector <pii> A[NMAX];
priority_queue <pii> H;
pii nod;
bool viz[NMAX];
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
void read()
{
	in>>n>>m;
	int i,x,y,z;
	for (i=1; i<=m; i++)
	{
		in>>x>>y>>z;
		A[x].pb(mp(y,z));
	}
}
void solve()
{
	H.push(mp(0,1)); 
	int i,vec,cost;
	while (!H.empty())
	{
		nod=H.top();
		H.pop();
		if (!viz[nod.y])
		{
			best[nod.y]=-nod.x;
			viz[nod.y]=1;
			for (i=0; i<A[nod.y].size(); i++)
			{
				vec=A[nod.y][i].x; cost=A[nod.y][i].y;
				if (!viz[vec])
					H.push(mp(nod.x-cost,vec));
			}
		}
	}
	for (i=2; i<=n; i++)
		out<<best[i]<<' ';
	out<<'\n';
}
int main()
{
	freopen("dijkstra.in","r",stdin);
	freopen("dijkstra.out","w",stdout);
	read();
	solve();
	return 0;
}