#include <bits/stdc++.h>
using namespace std;

vector<pair<long long,long long> > V[100000];

long long rs[100000], n, m;

void dijkstra(long long x)
{
	set<pair<long long,long long> > S;
	S.insert({0,x});
	rs[x] = 0;
	while (!S.empty())
	{
		long long nod = S.begin() -> second;
		S.erase(S.begin());
		for (long long it = 0; it < V[nod].size(); it++)
		{
			long long weight = V[nod][it].second;
			long long edge = V[nod][it].first;
			if (rs[nod] + weight < rs[edge])
			{
				if (rs[edge] != 100000000 )
					S.erase(S.find({rs[edge], edge}));
					
				rs[edge] = rs[nod] + weight;
				S.insert({rs[edge], edge});
			}
			
		}
	}
}

int main()
{
	ifstream fin("dijkstra.in");
	ofstream fout("dijkstra.out");
	fin>>n>>m;
	for (long long i = 0; i < m; i++)
	{
		long long a, b, c;
		fin>>a>>b>>c;
		V[a].push_back({b, c});
	}
	for (long long i = 0; i <= n ; i++)
	rs[i] = 100000000;
		dijkstra(1);
	for (long long i = 2; i <= n; i++)
	{
		if (rs[i] == 100000000 ) fout<<0<<" ";
			else fout<<rs[i]<<" ";	
	} 
	return 0;
}