#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("input.txt", "r", stdin);

    // Variables for input and graph processing
    int n, m, node, target, cost;
    char separator;

    // Data structures
    vector<int> processingTime;                  // Stores processing time for each node
    vector<int> indegree;                        // Keeps track of the number of prerequisites for each node
    vector<vector<array<int, 2>>> adjacencyList; // Graph adjacency list with [target, cost]
    vector<int> longestPathEnd;                  // Tracks the node with the longest path to the current node
    vector<int> distance;                        // Stores the longest path distance to each node
    vector<int> stack;                           // Stack for processing nodes

    while (cin >> n >> m) {
        // Resize and initialize data structures
        processingTime.resize(n, 0);
        indegree.resize(n, 0);
        adjacencyList.resize(n);
        longestPathEnd.resize(n, -1);
        distance.resize(n, 0);

        // Input processing times
        cin >> processingTime[0];
        for (int i = 1; i < n; ++i) {
            cin >> separator >> processingTime[i];
        }

        // Input edges and build the graph
        for (int i = 0; i < m; ++i) {
            cin >> node >> target >> cost;
            indegree[target]++;
            adjacencyList[node].push_back({target, cost});
        }

        // Process nodes to calculate the longest path
        for (int i = n - 1; i >= 0; --i) {
            stack.push_back(i); // Add current node to the stack
            while (!stack.empty()) {
                int currentNode = stack.back();
                stack.pop_back();

                // If prerequisites are satisfied
                if (--indegree[currentNode] == -1) {
                    distance[currentNode] += processingTime[currentNode];

                    // Process all adjacent nodes
                    for (auto &neighbor : adjacencyList[currentNode]) {
                        int nextNode = neighbor[0];
                        int edgeWeight = neighbor[1];

                        // Update distance and path information
                        if (distance[nextNode] < distance[currentNode] + edgeWeight) {
                            longestPathEnd[nextNode] = (longestPathEnd[currentNode] == -2) ? -2 : currentNode;
                            distance[nextNode] = distance[currentNode] + edgeWeight;
                        } else if (distance[nextNode] == distance[currentNode] + edgeWeight) {
                            longestPathEnd[nextNode] = -2; // Mark ambiguous paths
                        }

                        stack.push_back(nextNode); // Add to stack for processing
                    }
                }
            }
        }

        // Find the node with the maximum distance
        int endNode = max_element(distance.begin(), distance.end()) - distance.begin();
        cout << distance[endNode];

        // Check if the longest path is unique
        if (longestPathEnd[endNode] != -2 && count(distance.begin(), distance.end(), distance[endNode]) == 1) {
            // Reconstruct the path
            stack.push_back(endNode);
            while (stack.back() != -1) {
                stack.push_back(longestPathEnd[stack.back()]);
            }
            stack.pop_back(); // Remove the invalid -1 marker

            // Output the path
            while (!stack.empty()) {
                cout << "," << stack.back();
                stack.pop_back();
            }
            cout << "\n";
        } else {
            cout << ",M\n"; // Ambiguous path
        }
    }

    return 0;
}