// Gokuri

#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
#include <map>
#include <set>
#include <string>
#include <cmath>
#include <cctype>
#include <queue>

using namespace std;

#define FNAME "acm.txt"
#define fin cin

typedef int vert;
struct cost_t {
  int offset, period;
  int length;
};
typedef int len_t;
typedef vector< pair<vert, cost_t> > edges;
typedef vector< edges > graph;

class ToIntR {
  map<string, int> mp;
  vector<string>   idmap;
  int id;
public:
  ToIntR(int id = 0) : id(id) {}
  int operator[] (const string& s) {
    if(!mp.count(s)) idmap.push_back(s);
    return mp.count(s) ? mp[s] : (mp[s] = id++);
  }
  string id2value(int id) const { return idmap[id]; }
  size_t size() const { return idmap.size(); }
};

string get_time(int tm)
{
  static char buffer[32];
  
  tm %= 24 * 60;
  
  int min = tm % 60;
  tm /= 60;
  bool pm = tm >= 12;
  if(pm) tm -= 12;
  if(!tm) tm += 12;
  
  sprintf(buffer, "%u:%02u %cM",
          tm, min, pm ? 'P' : 'A');
  return string(buffer);
}

typedef pair<int, vert> cedge;
int simulate(const graph& g, vert cur, vert dst, int time)
{
  priority_queue< cedge, vector<cedge>, greater<cedge> > Q;
  map<vert, int> shtstlen;
  
  Q.push(cedge(time, cur));
  while(!Q.empty()) {
    cedge ce = Q.top(); Q.pop();
    if(shtstlen.count(ce.second))
      continue;
    shtstlen[ce.second] = ce.first;
    if(ce.second == dst) {
      break;
    }
    
    const edges ne = g[ce.second];
    for(int i = 0; i < ne.size(); i++) {
      if(!shtstlen.count(ne[i].first)) continue;
      
      const cost_t& c = ne[i].second;
      int lt = ((ce.first - c.offset) + c.period - 1) / c.period * c.period + c.offset;
      lt += c.length + 15;
      Q.push(cedge(lt, ne[i].first));
    }
  }
  
  int mx = INT_MIN;
  for(map<vert,int>::const_iterator it = shtstlen.begin();
      it != shtstlen.end();
      ++it)
    mx = max(it->second, mx);
  return mx;
}

void solve(const graph& g, const ToIntR& name_map)
{
  int result_len = 0;
  pair<vert, vert> result;
  pair<int, int>   result_time;
  
  for(int i = 0; i < g.size(); i++) {
    vector<bool> visited(g.size());
    visited[i] = true;
    
    for(int j = 0; j < g[i].size(); j++) {
      if(i == g[i][j].first) abort();
      
      const cost_t& c = g[i][j].second;
      for(int lt = c.offset + 1; lt < 24 * 60; lt += c.period) {
        for(int k = 0; k < g[i].size(); k++) {
          const int curtime = lt + c.length + 15;
          int endtime = simulate(g, i, k, curtime) - 15;
          if(endtime - lt > result_len) {
            result_len = endtime - lt;
            result = make_pair(i, g[i][j].first);
            result_time = make_pair(lt, endtime);
          }
        }
      }
    }
  }
  
  cout
    << "Longest trip: " << result_len
    << (result_len == 1 ? "minute" : " minutes") << endl;
  cout
    << "Origin " << name_map.id2value(result.first) << ' ' << get_time(result_time.first)
    << ", " << name_map.id2value(result.second) << ' ' << get_time(result_time.second)
    << endl;
}

int main(void)
{
  ifstream fin(FNAME);
  if (!fin) { return 1; }

  // INPUT HERE
  int ncase = 0;
  int n;
  while(cin >> n, n) {
    ToIntR name_map;
    graph g;
    while(n--) {
      string src, dst;
      int first, period, len;
      cin >> src >> dst >> first >> period >> len;
      
      // constr. graph
      if(name_map[src] >= g.size())
        g.resize(name_map[src] + 1);
      if(name_map[dst] >= g.size())
        g.resize(name_map[dst] + 1);
      
      cost_t c = {first, period, len};
      g[name_map[src]].push_back(make_pair(name_map[dst], c));
    }
    
    cout << "Input set " << ++ncase << ":" << endl;
    solve(g, name_map);
    cout << endl;
  }
  
  return 0;
}