import Algorithms as algo;
import Mathematics as math;
import Text as text;

class Edge {
	_to = none;
	_name = none;
	_cost = none;
	constructor( to_, name_, cost_ ) {
		_to = to_;
		_name = name_;
		_cost = real( cost_ );
	}
	to_string() {
		return ( "{}<{}>".format( _name, _cost ) );
	}
}

class Path {
	_id = none;
	_from = none;
	_cost = none;
	_names = none;
	constructor( toName_, ids_, names_ ) {
		_id = ids_[toName_];
		_names = names_;
		_cost = math.INFINITY;
	}
	less( other_ ) {
		return ( _cost < other_._cost );
	}
	update( from_, cost_ ) {
		_from = from_;
		_cost = cost_;
	}
	to_string() {
		return ( "{} via {} at cost {}".format( _names[_id], _from != none ? _names[_from] : none, _cost ) );
	}
}

class Graph {
	_neighbours = [];
	_ids = {};
	_names = [];
	add_node( name_ ) {
		if ( name_ ∉ _ids ) {
			_ids[name_] = size( _names );
			_names.push( name_ );
		}
	}
	add_edge( from_, to_, cost_ ) {
		assert( ( from_ ∈ _ids ) && ( to_ ∈ _ids ) );
		from = _ids[from_];
		to = _ids[to_];
		if ( from >= size( _neighbours ) ) {
			_neighbours.resize( from + 1, [] );
		}
		_neighbours[from].push( Edge( to, to_, cost_ ) );
	}
	shortest_paths( from_ ) {
		assert( from_ ∈ _ids );
		from = _ids[from_];
		paths = algo.materialize( algo.map( _names, @[_ids, _names]( name ) { Path( name, _ids, _names ); } ), list );
		paths[from].update( none, 0.0 );
		todo = algo.sorted( paths, @(x){-x._cost;} );
		while ( size( todo ) > 0 ) {
			node = todo[-1]._id;
			todo.resize( size( todo ) - 1, none );
			if ( node >= size( _neighbours ) ) {
				continue;
			}
			neighbours = _neighbours[node];
			for ( n : neighbours ) {
				newCost = n._cost + paths[node]._cost;
				if ( newCost < paths[n._to]._cost ) {
					paths[n._to].update( node, newCost );
				}
			}
			todo = algo.sorted( todo, @(x){-x._cost;} );
		}
		return ( paths );
	}
	path( paths_, to_ ) {
		assert( to_ ∈ _ids );
		to = _ids[to_];
		p = [to_];
		while ( paths_[to]._from != none ) {
			to = paths_[to]._from;
			p.push( _names[to] );
		}
		return ( algo.materialize( algo.reversed( p ), list ) );
	}
	to_string() {
		s = "";
		for ( i, n : algo.enumerate( _neighbours ) ) {
			s += "{} -> {}\n".format( _names[i], n );
		}
	}
}

main() {
	g = Graph();
	confStr = input();
	if ( confStr == none ) {
		return ( 1 );
	}
	conf = algo.materialize( algo.map( text.split( confStr ), integer ), tuple );
	assert( size( conf ) == 2 );
	for ( _ : algo.range( conf[0] ) ) {
		line = input();
		if ( line == none ) {
			return ( 1 );
		}
		g.add_node( line.strip() );
	}
	for ( _ : algo.range( conf[1] ) ) {
		line = input();
		if ( line == none ) {
			return ( 1 );
		}
		g.add_edge( algo.materialize( text.split( line.strip() ), tuple )... );
	}
	print( string( g ) );
	paths = g.shortest_paths( "a" );
	for ( p : paths ) {
		print( "{}\n".format( p ) );
	}
	print( "{}\n".format( g.path( paths, "e" ) ) );
	print( "{}\n".format( g.path( paths, "f" ) ) );
}