import java.io.*;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Main {
    static InputStreamReader isr = new InputStreamReader(System.in);
    static BufferedReader in = new BufferedReader(isr);
    static OutputStreamWriter osw = new OutputStreamWriter(System.out);
    static BufferedWriter out = new BufferedWriter(osw);

    //存储城市名与编号的映射关系
    static Map<String, Integer> n2i = new HashMap<>();
    static Map<Integer, String> i2n = new HashMap<>();

    //稀疏图，用邻接表存储
    static final int N = 220, K = 550;
    static int idx, hidx, n, k, start, end;
    static int[] h = new int[N];
    static int[] e = new int[K];
    static int[] ne = new int[K];
    static int[] we = new int[K];

    //每个城市的幸福指数
    static int[] ve = new int[N];
    //最短路距离
    static int[] dist = new int[N];
    //最短路径
    static int[] path = new int[N];
    //到达当前点的最短路径条数
    static int[] cntP = new int[K];
    //到达当前点所经过的城市数
    static int[] cnt = new int[N];
    //到达当前点的幸福值
    static int[] pv = new int[N];
    //标记是否已纳入最短路
    static boolean[] flag = new boolean[N];

    static {
        Arrays.fill(h, -1);
        Arrays.fill(path, -1);
        Arrays.fill(dist, 0x3f3fffff);
    }

    static void insert(String n1, String n2, int w) {
        int id1 = n2i.get(n1);
        int id2 = n2i.get(n2);

        e[hidx] = id2;
        ne[hidx] = h[id1];
        we[hidx] = w;
        h[id1] = hidx++;

        e[hidx] = id1;
        ne[hidx] = h[id2];
        we[hidx] = w;
        h[id2] = hidx++;
    }

    static void dijkstra() {
        dist[start] = 0;
        cntP[start] = 1;
        for (int i = 0; i < idx; i++) {
            int minDist = 0x3f3fffff, minId = -1;
            for (int j = 0; j < idx; j++) {
                if (!flag[j] && dist[j] < minDist) {
                    minDist = dist[j];
                    minId = j;
                }
            }
            int pivot = minId;
            //找到第一条最短路
            cntP[pivot] = Math.max(1, cntP[pivot]);
            flag[pivot] = true;
            for (int j = h[pivot]; j != -1; j = ne[j]) {
                int next = e[j];
                //未确定最短路，且可以更新
                if (!flag[next] && dist[next] > dist[pivot] + we[j]) {
                    dist[next] = dist[pivot] + we[j];
                    path[next] = pivot;
                    cnt[next] = cnt[pivot] + 1;
                    cntP[next] = cntP[pivot];
                    pv[next] = pv[pivot] + ve[next];
                }
                //找到相同距离路径
                else if (dist[next] == dist[pivot] + we[j]) {
                    //到此城市的最短路径数量更新
                    cntP[next] += cntP[pivot];
                    //如果新路径幸福值更高，更新路径
                    if (pv[next] < pv[pivot] + ve[next]) {
                        pv[next] = pv[pivot] + ve[next];
                        path[next] = pivot;
                        cnt[next] = cnt[pivot] + 1;
                    }
                    //如果新路径幸福值与原路径相等，但新路径经过的城市数更少
                    else if (pv[next] == pv[pivot] + ve[next] && cnt[next] > cnt[pivot] + 1) {
                        path[next] = pivot;
                        cnt[next] = cnt[pivot] + 1;
                    }
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        String[] strs = in.readLine().split(" ");
        n = Integer.parseInt(strs[0]);
        k = Integer.parseInt(strs[1]);
        String name = strs[2];
        n2i.put(name, idx);
        i2n.put(idx++, name);
        for (int i = 1; i < n; i++) {
            strs = in.readLine().split(" ");
            name = strs[0];
            ve[idx] = Integer.parseInt(strs[1]);
            n2i.put(name, idx);
            i2n.put(idx++, name);
        }

        for (int i = 0; i < k; i++) {
            strs = in.readLine().split(" ");
            String n1 = strs[0];
            String n2 = strs[1];
            int w = Integer.parseInt(strs[2]);
            insert(n1, n2, w);
        }
        start = 0;
        end = n2i.get("ROM");
        dijkstra();

        out.write(String.format("%d %d %d %d\n", cntP[end], dist[end], pv[end], pv[end] / cnt[end]));
        int id = 0;
        //总点的数量为经过的城市数加原点
        int num = cnt[end] + 1;
        int[] op = new int[num];
        op[id++] = end;
        for (int i = path[end]; i != -1; i = path[i]) op[id++] = i;
        for (int i = cnt[end]; i > 0; i--)
            out.write(i2n.get(op[i]) + "->");
        out.write(i2n.get(op[0]));
        in.close();
        isr.close();
        out.flush();
        out.close();
        osw.close();
    }
}