#include <map>
#include<climits>
using namespace std;
class des{
public:
des(){
value=INT_MAX;
fromID=-1;
fConnect=false;
passbyID=-1;
};
int value;
int fromID;
int passbyID;
bool fConnect;
string route;
};
int to_int(char const *s)
{
if ( s == NULL || s[0] == '\0' )
{
return 0;
}
bool negate = (s[0] == '-');
if ( *s == '+' || *s == '-' )
++s;
int result = 0;
while(*s)
{
if ( *s >= '0' && *s <= '9' )
{
result = result * 10 - (*s - '0');
}
else
return 0;
++s;
}
return negate ? result : -result;
}
void Floyd_Warshall(des arrDes[101][101],int nAirportNum){
for(int k=1;k<=nAirportNum;k++){
for(int i=1;i<=nAirportNum;i++){
for(int j=1;j<=nAirportNum;j++){
if(arrDes[i][k].fConnect&&arrDes[k][j].fConnect){
int temp=arrDes[i][k].value + arrDes[k][j].value;
if(temp<arrDes[i][j].value){
arrDes[i][j].value=temp;
arrDes[i][j].passbyID=k;
arrDes[i][j].fConnect=true;
}
}
}
}
}
}
void printPath(des arrDes[101][101],int fromID,int toID,map<int,string> airport){
if(arrDes[fromID][toID].passbyID==fromID){
cout.flags(ios::left);
string from=airport.find(fromID)->second;
string to=airport.find(toID)->second;
cout.width(21);
cout<<from;
cout.width(21);
cout<<to;
cout.width(11);
cout<<arrDes[fromID][toID].route;
cout.width(5);
cout.flags(ios::right);
cout<<arrDes[fromID][toID].value<<endl;
}
else{
int passbyID=arrDes[fromID][toID].passbyID;
printPath(arrDes,fromID,passbyID,airport);
if(arrDes[passbyID][toID].passbyID==passbyID){
cout.flags(ios::left);
string from=airport.find(passbyID)->second;
string to=airport.find(toID)->second;
cout.width(21);
cout<<from;
cout.width(21);
cout<<to;
cout.width(11);
cout<<arrDes[passbyID][toID].route;
cout.flags(ios::right);
cout.width(5);
cout<<arrDes[passbyID][toID].value<<endl;
}
else
printPath(arrDes,passbyID,toID,airport);
}
}
int main(){
char bufc[256];
map<string,int> airportNameToID;
map<int,string> airportIDToName;
int nAirportNum=0;
des arrDes[101][101];
while(cin.getline(bufc,256)){
string bufs(bufc);
if(bufs=="")break;
std::size_t found=bufs.find(",",0);
string from=bufs.substr(0,found);
bufs=bufs.substr(found+1,bufs.length());
found=bufs.find(",",0);
string to=bufs.substr(0,found);
bufs=bufs.substr(found+1,bufs.length());
found=bufs.find(",",0);
string route=bufs.substr(0,found);
bufs=bufs.substr(found+1,bufs.length());
found=bufs.find(",",0);
string miles=bufs.substr(0,found);
bufs=bufs.substr(found+1,bufs.length());
int fromID,toID;
if(airportNameToID.find(from)!=airportNameToID.end()){
fromID=airportNameToID.find(from)->second;
}
else{
nAirportNum++;
fromID=nAirportNum;
airportNameToID.insert(pair<string,int>(from,fromID));
airportIDToName.insert(pair<int,string>(fromID,from));
}
if(airportNameToID.find(to)!=airportNameToID.end()){
toID=airportNameToID.find(to)->second;
}
else{
nAirportNum++;
toID=nAirportNum;
airportNameToID.insert(pair<string,int>(to,toID));
airportIDToName.insert(pair<int,string>(toID,to));
}
int nValue=to_int(miles.c_str());
if(arrDes[fromID][toID].value>nValue){
arrDes[fromID][toID].value=nValue;
arrDes[fromID][toID].route=route;
arrDes[fromID][toID].fromID=fromID;
arrDes[fromID][toID].passbyID=fromID;
arrDes[fromID][toID].fConnect=true;
arrDes[toID][fromID].value=nValue;
arrDes[toID][fromID].route=route;
arrDes[toID][fromID].fromID=toID;
arrDes[toID][fromID].passbyID=toID;
arrDes[toID][fromID].fConnect=true;
}
}
Floyd_Warshall(arrDes,nAirportNum);
while(cin.getline(bufc,255)){
string bufs(bufc);
cout<<endl<<endl;
std::size_t found=bufs.find(",",0);
string from=bufs.substr(0,found);
string to=bufs.substr(found+1,bufs.length());
int fromID=airportNameToID.find(from)->second;
int toID=airportNameToID.find(to)->second;
cout<<"From To Route Miles"<<endl;
cout<<"-------------------- -------------------- ---------- -----"<<endl;
printPath(arrDes,fromID,toID,airportIDToName);
cout<<" -----"<<endl;
cout.flags(ios::left);
cout.width(42);
cout<<"";
cout.width(11);
cout<<"Total";
cout.flags(ios::right);
cout.width(5);
cout<<arrDes[fromID][toID].value<<endl;
}
return 0;
}