+#include <assert.h>
+#include <stdio.h>
+#include <string.h>
+
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+
+using namespace std;
+
+#define INFINITY 10000
+
+vector<string> places;
+set<string> places_set;
+map<pair<string, string>, int> sparse_dist;
+
+int* dist;
+
+void check_name_inserted(char* name)
+{
+ if (places_set.count(name) == 0) {
+ places_set.insert(name);
+ places.push_back(name);
+ }
+}
+
+void make_matrix()
+{
+ int num_places = places.size();
+ dist = new int[num_places * num_places];
+
+ for (int i = 0; i < num_places; ++i) {
+ dist[i * num_places + i] = 0;
+ }
+
+ for (int i = 0; i < num_places; ++i) {
+ for (int j = i + 1; j < num_places; ++j) {
+ int d = INFINITY;
+
+ pair<string, string> comb = make_pair(places[i], places[j]);
+ if (sparse_dist.count(comb) != 0) {
+ d = sparse_dist[comb];
+ }
+ comb = make_pair(places[j], places[i]);
+ if (sparse_dist.count(comb) != 0) {
+ d = sparse_dist[comb];
+ }
+ dist[i * num_places + j] = d;
+ dist[j * num_places + i] = d;
+ }
+ }
+}
+
+void print_matrix()
+{
+ int num_places = places.size();
+ for (int i = 0; i < num_places; ++i) {
+ printf("%d: %s\n", i, places[i].c_str());
+ }
+ for (int i = 0; i < num_places; ++i) {
+ for (int j = 0; j < num_places; ++j) {
+ printf("%5d ", dist[i * num_places + j]);
+ }
+ printf("\n");
+ }
+}
+
+void floyd_warshall()
+{
+ int num_places = places.size();
+
+ for (int k = 0; k < num_places; ++k) {
+ for (int i = 0; i < num_places; ++i) {
+ for (int j = 0; j < num_places; ++j) {
+ dist[i * num_places + j] =
+ min(dist[i * num_places + j],
+ dist[i * num_places + k] + dist[k * num_places + j]);
+ }
+ }
+ }
+}
+
+int *cache;
+int cache_size;
+int best_cost;
+int finish_mask;
+
+void init_tsp()
+{
+ int num_places = places.size();
+ cache_size = (1 << num_places);
+ cache = new int[cache_size * num_places];
+
+ for (int i = 0; i < cache_size * num_places; ++i) {
+ cache[i] = -1;
+ }
+
+ best_cost = INFINITY;
+ finish_mask = (1 << num_places) - 1;
+}
+
+int tsp(int node_num, int visited_mask, int cost_so_far)
+{
+ int num_places = places.size();
+ if (cache[node_num * cache_size + visited_mask] != -1) {
+ return cache[node_num * cache_size + visited_mask];
+ }
+ if (cost_so_far > best_cost) {
+ return INFINITY;
+ }
+
+ if (visited_mask == finish_mask) {
+ return 0;
+/*
+ cost_so_far += dist[node_num * num_places + 0];
+ cache[node_num * cache_size + visited_mask] = dist[node_num * num_places + 0];
+ if (cost_so_far < best_cost) {
+ best_cost = cost_so_far;
+ }
+ return dist[node_num * num_places + 0]; */
+ }
+
+ int best_this_cost = INFINITY;
+ for (int i = 0; i < num_places; ++i) {
+ if (visited_mask & (1 << i)) {
+ continue;
+ }
+
+ int cost = dist[node_num * num_places + i]
+ + tsp(i, visited_mask | (1 << i), cost_so_far + dist[node_num * num_places + i]);
+ if (cost < best_this_cost) {
+ best_this_cost = cost;
+ }
+ }
+
+ cache[node_num * cache_size + visited_mask] = best_this_cost;
+ return best_this_cost;
+}
+
+void backtrack(int node_num, int visited_mask)
+{
+ int num_places = places.size();
+ if (visited_mask == finish_mask) {
+ return;
+ }
+
+ int best_node = 0;
+ int best_this_cost = INFINITY;
+ for (int i = 0; i < num_places; ++i) {
+ if (visited_mask & (1 << i)) {
+ continue;
+ }
+
+ int cost = dist[node_num * num_places + i] +
+ cache[i * cache_size + (visited_mask | (1 << i))];
+ assert(cost != -1);
+ if (cost < best_this_cost) {
+ best_node = i;
+ best_this_cost = cost;
+ }
+ }
+
+ printf("%s [%d] [%d to %d costs %d]\n", places[best_node].c_str(), best_this_cost, node_num, best_node, dist[node_num * num_places + best_node]);
+ backtrack(best_node, visited_mask | (1 << best_node));
+}
+
+int main(void)
+{
+ for ( ;; ) {
+ char name1[256];
+ char name2[256];
+ int dist;
+
+ if (scanf("%s %s %d", name1, name2, &dist) != 3) {
+ break;
+ }
+
+ check_name_inserted(name1);
+ check_name_inserted(name2);
+ sparse_dist.insert(make_pair(make_pair(name1, name2), dist));
+ }
+
+ make_matrix();
+ print_matrix();
+ printf("\n");
+ floyd_warshall();
+ print_matrix();
+
+ init_tsp();
+ tsp(0, 1, 0);
+ printf("fg [%d]\n", best_cost);
+ backtrack(0, 1);
+}