#!/usr/bin/perl -w

use v5.16;
use strict;

$; = ',';

my %route;
my %cities;
while (<>) {
	my ($src, $dst, $len) = /^(\w+) to (\w+) = (\d+)/;
	$cities{$src} = $cities{$dst} = 1;
	$route{$src,$dst} = $len;
	$route{$dst,$src} = $len;
}


my $max_dist;
sub do_perm {
	my ($path, $dist, $rest) = @_;
	
	if (!@$rest) {
		$max_dist = $dist if !$max_dist || $dist > $max_dist;
		say "new min $max_dist";
		return;
	}
	for my $i (0 .. $#$rest) {
		my @nrest = @$rest;
		my ($next) = splice (@nrest, $i, 1);
		my @npath = (@$path, $next);
		my $ndist = $dist;
		if (@$path) {
			my $prev = $path->[-1];
			$ndist += $route{$prev,$next};
		}
		# say join(',', @npath), " $ndist";
		do_perm(\@npath, $ndist, \@nrest);
	}
}

do_perm([], 0, [ keys %cities ]);
say $max_dist;

