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

using namespace std;

const char iname[] = "dijkstra.in";
const char oname[] = "dijkstra.out";
const int  nmax    = 50005;

ifstream fin(iname);
ofstream fout(oname);

int n, m, i, j, k, c, x, y;
vector<pair <int, int> > Gr[nmax];
queue<int> Q;
int D[nmax];
int viz[nmax];

void dijkstra()
{	
	for(i = 2; i <= n; i ++)
		D[i] = 28717878;
	Q.push(1);
	viz[1] = 1;
	while(!Q.empty())
	{	
		x = Q.front();
		Q.pop();
		for(i = 0; i < Gr[x].size(); i ++)
			if(viz[Gr[x][i].first] == 0)
				if(D[Gr[x][i].first] > D[x] + Gr[x][i].second)
				{
					D[Gr[x][i].first] = D[x] + Gr[x][i].second;
					Q.push(Gr[x][i].first);
					viz[Gr[x][i].first] = 1;
				}
	}
}


int main()
{
	fin >> n >> m;
	for(i = 1; i <= m; i ++)
	{
		fin >> x >> y >> c;
		Gr[x].push_back(make_pair(y, c));
	}
	
	dijkstra();
	for(i = 2; i <= n; i ++)
		fout << D[i] << " ";
	return 0;
}