#include <fstream>
#include <cstring>
#include <vector>
#include <queue>
#define INFI 0x3f3f3f3f

using namespace std;

typedef pair <int, int> pii;

bool vis[50001];
int n, m, sol[50001];
vector <pii> g[50001];
priority_queue <pii, vector <pii>, greater<pii> > H;

int main()
{
	int i,a,b,c,x,y;
	vector <pii> :: iterator v;
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	fin>>n>>m;
	for (i = 0; i < m; ++i)
	{
		fin>>a>>b>>c;
		g[a].push_back(make_pair(c,b));
	}
	memset(sol,0x3f,sizeof(sol));
	sol[1]=0;
	H.push(make_pair(0,1));
	while (!H.empty())
	{
		y=H.top().first;
		x=H.top().second;
		H.pop();
		vis[x]=1;
		for (v = g[x].begin();v!=g[x].end();++v)
			if (y+v->first<sol[v->second])
			{
				sol[v->second]=y+v->first;
				H.push(make_pair(sol[v->second],v->second));
			}
        while (!H.empty()&&vis[H.top().second])
			H.pop();
	}
	for (i=2;i<=n;++i)
        if (sol[i]!=INFI)
            fout<<sol[i]<<" ";
        else
            fout<<"0 ";
	fout<<"\n";
	return 0;
}