#include <fstream>
#include <vector>
#include <set>
#define INF 0x3f3f3f3f
using namespace std;

const int MAXN = 50005;

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

int N, M;
int D[MAXN];
vector < pair <int, int> > G[MAXN];
set < pair <int, int> > S;

void ReadData()
{
	fin >> N >> M;
	for (int i = 1; i <= M; ++i)
	{
		int a, b, c;
		fin >> a >> b >> c;
		G[a].push_back( make_pair(b, c) );
	}
	for (int i = 2; i <= N; ++i)
		D[i] = INF;
}

void Solve()
{
	S.insert( make_pair(0, 1) );
	while (!S.empty())
	{
		int node = S.begin() -> second;
		S.erase( S.begin() );
		for (vector < pair <int, int> > :: iterator it = G[node].begin(); it != G[node].end(); ++it)
		{
			int vecin = it -> first;
			int cost = it -> second;
			if (D[vecin] > D[node] + cost)
			{
				if (D[vecin] != INF) S.erase( make_pair(D[vecin], vecin) );
				D[vecin] = D[node] + cost;
				S.insert( make_pair(D[vecin], vecin) );
			}
		}
	}
}

void WriteData()
{
	for (int i = 2; i <= N; ++i)
	{
		if (D[i] != INF) fout << D[i] << " ";
		else 			 fout << "0 ";
	}
}

int main()
{
	ReadData();
	Solve();
	WriteData();
	fin.close();
	fout.close();
	return 0;
}