#include <utility>
#include <vector>
#include <fstream>
#include <queue>
using namespace std;

#define pb push_back
#define mp make_pair

const int INF = 500000000;
const int NMAX = 50005;
const char Input[] = "dijkstra.in";
const char Output[] = "dijkstra.out";

vector<int> g[NMAX],c[NMAX];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater< pair <int,int> > > H;
int N,M,dmin[NMAX];
ifstream fin(Input);
ofstream fout(Output);

void read()
{
	int i,e1,e2,cost;
	
	fin>>N>>M;
	
	for(i=1; i<=M; i++)
	{
		fin>>e1>>e2>>cost;
		g[e1].pb(e2);
		c[e1].pb(cost);
	}
}

void dijkstra()
{
	int nod , cost,i;
	
	for(i=2; i<=N; i++)
		dmin[i] = INF;
	
	H.push(mp(0,1));
	
	while(!H.empty())
	{
		cost = (H.top()).first;
		nod = (H.top()).second;
		H.pop();
		
		for(i=0; i<g[nod].size(); i++)
			if(dmin[g[nod][i]] > cost + c[nod][i])
			{
				dmin[g[nod][i]] = cost + c[nod][i];
				H.push(mp(dmin[g[nod][i]],g[nod][i]));
			}
	}
}

int main()
{
	read();
	dijkstra();
	
	int i;
	
	for(i=2; i<=N; i++)
		if(dmin[i] == INF)
			fout<<0<<" ";
		else
			fout<<dmin[i]<<" ";
	
	fin.close();
	fout.close();
	return 0;
}