#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <bitset>
#include <fstream>

#define NMAX 50005
#define DMAX 0xfffffff

using namespace std;

fstream fin("dijkstra.in", ios::in), fout("dijkstra.out", ios::out);

void read(),solve(),write();

typedef pair<unsigned int,unsigned int> pereche;
typedef list<pereche> lista;

struct cmp
{
	bool operator()(const pereche &a, const pereche &b)
	const
	{
		return a.second>b.second;
	}
};

lista G[NMAX];
vector<unsigned int> dist(NMAX,DMAX);
priority_queue<pereche,vector<pereche>,cmp>coada;
bitset<NMAX> verificat(0);

int N,M;

int main()
{	
	read();
	solve();
	write();	
	return 0;
}

void write()
{
	for(int i=2;i<=N;i++)
		cout<<nounitbuf<<(dist[i]!=DMAX?dist[i]:0)<<" ";
}

void solve()
{
	dist[1]=0;
	coada.push(pereche(1,0));
	
	while(!coada.empty())
	{
		pereche aux=coada.top();
		unsigned int nod=aux.first, cost=aux.second;
		coada.pop();
		if(!verificat[nod])
		{
			for(lista::iterator it=G[nod].begin();it!=G[nod].end();it++)
				if(dist[(*it).first]>cost+(*it).second)
				{
					dist[(*it).first]=cost+(*it).second;
					coada.push(pereche((*it).first,dist[(*it).first]));
				}
			verificat[nod]=true;
		}
	}
}

void read()
{
	fin >> N >> M;
	for(int i=0;i<M;i++)
	{
		int s,d,c;
		fin >> s >> d >> c;
		G[s].push_back(pereche(d,c));
	}
}