#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const char InFile[]="dijkstra.in";
const char OutFile[]="dijkstra.out";
const int MaxN=50005;
const int INF=100000000;

ifstream fin(InFile);
ofstream fout(OutFile);

struct s{int dest,cost;};


int N,M;
int d[MaxN];
int v[MaxN];
vector<s> a[MaxN];

void dijkstra(int nod)
{
	queue<int> q;
	q.push(nod);
	d[nod]=0;
	v[nod]=1;
	for(register int i=2;i<=N;++i)
	{
		d[i]=INF;
	}
	while(!q.empty())
	{
		nod=q.front();
		q.pop();
		for(register int i=0;i<(int)a[nod].size();++i)
		{
			if(v[a[nod][i].dest]==0)
			{
				v[a[nod][i].dest]=1;
				q.push(a[nod][i].dest);
			}
			if(d[nod]+a[nod][i].cost<d[a[nod][i].dest])
			{
				d[a[nod][i].dest]=d[nod]+a[nod][i].cost;
			}
		}
	}
}

s t;
int x,y,cost;

int main()
{
	fin>>N>>M;
	for(register int i=0;i<M;++i)
	{
		fin>>x>>y>>cost;
		t.cost=cost;
		t.dest=y;
		a[x].push_back(t);
	}
	fin.close();

	dijkstra(1);

	for(register int i=2;i<=N;++i)
	{
		fout<<d[i]<<" ";
	}
	fout.close();
	return 0;
}