#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
#define dim 50005
#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
int d[dim], viz[dim],n , m;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
vector < pair < int , int > > v[dim*2];

struct cmp
{
	bool operator () (const int &a, const int &b)const
	{
		return d[a]>d[b];
	}
};

priority_queue <int, vector <int> , cmp> Heap;

void read()
{
	int i, a, b, c;
	fin>>n >>m;
	for(i=1;i<=m;++i)
	{
		fin>>a >>b >>c;
		v[a].pb(mp(b,c));
	}
}

void dijkstra(int nod)
{
	memset(d,inf,sizeof(d));
	d[nod]=0;
	Heap.push(nod);
	viz[nod]=1;
	while(!Heap.empty())
	{
		int re=Heap.top();
		Heap.pop();
		viz[re]=0;
		
		for(int k=0;k<v[re].size();++k)
			if(d[re]+v[re][k].sc<d[v[re][k].fs])
			{
				d[v[re][k].fs]=d[re]+v[re][k].sc;
				if(viz[v[re][k].fs]==0)
				{
					viz[v[re][k].fs]=1;
					Heap.push(v[re][k].fs);
				}
			}
	}
	
	for(int i=2;i<=n;++i)
		if(d[i]==inf)
			fout<<"0" <<" ";
		else
			fout<<d[i] <<" ";
}

int main()
{
	
	read();
	dijkstra(1);
	
	return 0;
}