#include <iostream>
#include <string>
#include <fstream>
#include <map>
#include <cstdio>
#include <vector>
#include <climits>
#include <cassert>

using namespace std;

#define INFTY INT_MAX
#define ARRIVE_COST 15

class Line {
public:
	Line( int to, int first, int separation, int length ) : to(to), first(first), separation(separation), length(length) {}

	int getTo() const { return to; }

	int getArriveTime( int start ) {
		// start 時に出発した場合目的地に着くまでにどれだけかかるか.
		if ( start <= first ) return first - start + length;
		const int m = (start - first) % separation;
		return (m == 0)? length : (separation - m + length);
	}

private:
	int to, first, separation, length;

};

class Station {
public:
	Station( const string &name ) : name(name) {}
	void addLine( const Line &line ) { lines.push_back(line); }
	const string &getName() const { return name; }

	int getNextLine( int start, int to ) {
		int earliest = INFTY;
		for ( int i = 0; i < lines.size(); i++ )
			if ( lines[i].getTo() == to ) earliest = min(earliest, lines[i].getArriveTime(start));
		return earliest;
	}

private:
	string name;
	vector<Line> lines;

};

vector<Station> S;

int getID( const string &name, map<string, int> &M ) {
	if ( M.find(name) != M.end() ) return M[name];
	const int id = M.size();
	M[name] = id;
	S.push_back(Station(name));
	return id;
}

string toTimeString( int t ) {
	int min = t % 60;
	int hour = (t / 60) % 12;
	if ( hour == 0 ) hour = 12;

	char buf[16];
	sprintf(buf, "%d:%02d %s", hour, min, (t >= 12*60)? "PM" : "AM");
	return buf;
}

// start 分に from から出発して最も遅く届くのはどこでどのぐらいの時間がかかるのか.
// pair<目的地, かかる時間(min)>
pair<int, int> computeLongest( int from, int start ) {
	vector<int> D(S.size(), INFTY);
	vector<bool> visited(S.size(), false);

	D[from] = 0;
	for ( int n = 0; n < S.size(); n++ ) {
		int minDist = INFTY, minNode;
		for ( int u = 0; u < S.size(); u++ )
			if ( !visited[u] && minDist > D[u] ) minDist = D[u], minNode = u;

		assert( minDist != INFTY );
		visited[minNode] = true;

		const int u = minNode, t = D[u];
		for ( int v = 0; v < S.size(); v++ ) {
			if ( visited[v] ) continue;
			const int nextLine = S[u].getNextLine((start+t)%(24*60), v);
			if ( nextLine == INFTY ) continue;
			if ( D[v] > t + nextLine + ARRIVE_COST ) D[v] = t + nextLine + ARRIVE_COST;
		}
	}

	int longest = 0, to;
	for ( int u = 0; u < S.size(); u++ )
		if ( longest < D[u] ) longest = D[u], to = u;
	return make_pair(to, longest);
}

int main() {
	int nline;
	string from, to;
	int first, separation, length;

	ifstream cin("acm.txt");

	for ( int nt = 1; cin >> nline, nline; nt++ ) {
		map<string, int> name2id;

		S.clear();
		for ( int n = 0; n < nline; n++ ) {
			cin >> from >> to >> first >> separation >> length;
			const int fromID = getID(from, name2id);
			const int toID = getID(to, name2id);
			S[fromID].addLine(Line(toID, first, separation, length));
		}

		int longest = -1, longestFrom, longestTo, longestStart;
		for ( int t = 0; t < 24*60; t++ )
			for ( int from = 0; from < S.size(); from++ ) {
				const pair<int, int> result = computeLongest(from, t);
				if ( result.second > longest )
					longest = result.second, longestFrom = from, longestTo = result.first, longestStart = t;
			}

		cout << "Input set " << nt << ":" << endl;
		cout << "Longest trip: " << longest << " minutes" << endl;
		cout << "Origin " << S[longestFrom].getName() << " " << toTimeString(longestStart) << ", ";
		cout << "destination " << S[longestTo].getName() << " " << toTimeString((longestStart+longest)%(24*60)) << "." << endl;
		cout << endl;
	}

	return 0;
}