#include<fstream>
#include<queue>
#include<map>
#define MaxN 50005
#define INF 0x3f3f3f3f

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

map<int, int> G[MaxN];
queue<int> qu;
int n,m,a,b,c,d[MaxN],i,X;

void bellmanFord()
{	map<int, int>::iterator it;
	memset(d, INF, sizeof(d));
	d[1]=0;
	qu.push(1);
	while(!qu.empty())
	{	X=qu.front();
		for(it=G[X].begin();it!=G[X].end();it++)
			if(d[X]+it->second<d[it->first])
			{	d[it->first]=d[X]+it->second;
				qu.push(it->first);
			}
		qu.pop();
	}
}

int main()
{	fin>>n>>m;
	for(i=1;i<=m;i++)
	{	fin>>a>>b>>c;
		G[a].insert(make_pair(b,c));
	}
	bellmanFord();
	for(i=2;i<=n;i++)
		fout<<d[i]<<' ';
}