#include <deque>
#include <iostream>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;

int parseID(string s) {
	return (s[0] - 'A') * ('Z' - 'A' + 1) + (s[1] - 'A');
}

// Fucking hell.
struct hash_pair {
	template<typename T1, typename T2>
	size_t operator()(const pair<T1, T2>& p) const
	{
		auto h1 = hash<T1>{}(p.first);
		auto h2 = hash<T1>{}(p.second);
		return h1 ^ (h2 << 1);
	}
};

struct Graph {
	unordered_multimap<int, int> conns;
	unordered_map<int, int> rates;

	unordered_map<pair<int, int>, int, hash_pair> dist;
};

void findLengths(Graph &g, int base) {
	deque<int> frontier;
	frontier.push_back(base);
	g.dist.insert({{base, base}, 0});
	while (!frontier.empty()) {
		// i love c++ i love c++ i love c++
		int from = frontier.front();
		int dist = g.dist[{base, from}];
		frontier.pop_front();
		auto range = g.conns.equal_range(from);
		for (auto it = range.first; it != range.second; it++) {
			int to = it->second;
			if (g.dist.count({base, to}) != 0)
				continue;
			g.dist.insert({{base, to}, dist + 1});
			frontier.push_back(to);
		}
	}
}

Graph g;

void rec(vector<int> path, vector<int> &avail, int time, int score) {
	cout << score << "\t" << time << "\t";
	for (int n : path)
		cout << n << ",";
	cout << endl;

	int cur = path.back();
	for (int i = 0; i < avail.size(); i++) {
		int n = avail[i];
		if (n == 0) continue;
		avail[i] = 0;

		vector<int> path2 = path;
		path2.push_back(n);

		int time2 = time + g.dist[{cur, n}] + 1;
		if (30 < time2) continue;
		int score2 = score + g.rates[n] * (30 - time2);

		rec(path2, avail, time2, score2);
		avail[i] = n;
	}
}

int main() {
	vector<int> nonzero;
	for (string s; getline(cin, s); ) {
		auto numStart = s.find('=') + 1;
		auto numEnd = s.find(';', numStart) - numStart;

		int from = parseID(s.substr(6, 2));
		int rate = stoi(s.substr(numStart, numEnd));

		g.rates[from] = rate;
		if (rate != 0) nonzero.push_back(from);

		s = s.substr(s.find(' ', s.find("valve")) + 1);
		for (int i = 0; i + 2 <= s.size(); i += 4) {
			int to = parseID(s.substr(i, 2));
			g.conns.insert({from, to});
		}
	}

	findLengths(g, 0);
	for (int base : nonzero)
		findLengths(g, base);

	vector<int> start = {0};
	rec(start, nonzero, 0, 0);
}