#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <stack>

using namespace std;

void SearchAdd (string [], string, int &, int &);

int main ()
{
	int			dist[20];
	int			delay;
	string		to;
	string		from;
	string		airports[20];
	int			used[20] = {0};
	int			cost[20][20];
	int			f, t;
	int			acount = 2;
	ifstream	infile;
	int			least;
	int			which;
	int			last[20];
	stack<string>	route;

	infile.open("flights.txt");
	for (f = 0; f < 20; f++)
		for (t = 0; t < 20; t++)
			cost[f][t] = 1000000000;
	cost[0][0] = 0;
	airports[0] = "PIT";
	airports[1] = "SJO";
	used[0] = 1;
	infile >> from >> to;
	while (!infile.eof())
	{
		delay = 60;
		if (from == "PIT")
			infile >> delay;
		SearchAdd (airports, from, f, acount);
		SearchAdd (airports, to, t, acount);
		infile >> cost[f][t];
		cost[f][t] += delay;
		infile >> from >> to;
	}
	for (t = 0; t < acount; t++)
	{
		dist[t] = cost[0][t];
		last[t] = 0;
	}
	for (f = 1; f < acount; f++)
	{
		least = 1000000000;
		for (t = 1; t < acount; t++)
			if (used[t] == 0 && dist[t] < least)
			{
				least = dist[t];
				which = t;
			}
		used[which] = 1;
		for (t = 1; t < acount; t++)
			if (used[t] == 0)
			{
				least = dist[t];
				if (dist[t] > dist[which] + cost[which][t])
				{
					least = dist[which] + cost[which][t];
					last[t] = which;
				}
				dist[t] = least;
			}
	}
	which = last[1];
	route.push(airports[1]);
	while (which != 0)
	{
		route.push(airports[which]);
		which = last[which];
	}
	cout << "Route:  PIT";
	while (!route.empty())
	{
		cout << setw(5) << route.top();
		route.pop();
	}
	cout << endl << endl << "Elapsed time:  "  << dist[1] << " minutes" << endl;
//	for (t = 1; t < acount; t ++)
//		cout << airports[t] << "  " << dist[t] << "  " << last[t] << endl;
	return 0;
}

void SearchAdd (string  airports[], string look, int & where, int &howMany)
{
	for (where = 0; where < howMany; where++)
		if (airports[where] == look)
			return;
	airports[howMany] = look;
	howMany++;
}