#include "pch.h"
#include <fstream>
#include <iostream>
#include <set>
#include <cassert>
#include <vector>
std::ifstream fin("dijkstra.in");
std::ofstream fout("dijkstra.out");

const auto NMAX = 50005, INF = 0x3f3f3f3f;

std::vector< std::pair<int, int >> G[NMAX];
int dist[NMAX];
int main()
{
	int n, m;
	fin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int from, to, cost;
		fin >> from >> to >> cost;
		G[from].push_back(std::make_pair(to, cost));
	}
	memset(dist, INF, sizeof dist);
	dist[1] = 0;
	std::set< std::pair<int,int> > s;
	s.insert(std::make_pair(0, 1));

	while (!s.empty())
	{
		int node = s.begin()->second;
		int d = s.begin()->first;
		s.erase(s.begin());
		for (std::vector<std::pair<int, int>>::iterator it = G[node].begin(); it != G[node].end(); it++)
		{
			int to = it->first;
			int cost = it->second;
			if (dist[to] > dist[node] + cost){
				if (dist[to] != INF) 
					s.erase(s.find(std::make_pair(dist[to], to)));
				dist[to] = dist[node] + cost;
				s.insert(std::make_pair(dist[to], to));
				}
		}
	}

	for (int i = 2; i <= n; i++)
		if (dist[i] == INF)
			fout << 0 << " ";
		else
			fout << dist[i] << " ";
	
}