#include<bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int n,m,i,i2,a,b,c;
    char s;
    vector<int>v,v2,v1,v4,vd;
    //v1 la stack muitipurpuse
    //v la working time
    //v4 la longest last node -1 if none -2 if more than 2
    //vd distance
    //v2 la requerment
    vector<vector<array<int,2>>>v3;
    while(cin>>n>>m){
        v.resize(1);
        v2.resize(0);
        v3.resize(0);
        v4.resize(0);
        vd.resize(0);
        v2.resize(n,0);
        v3.resize(n);
        v4.resize(n,-1);
        vd.resize(n,0);
        cin>>v[0];
        for(i=n;--i;)cin>>s>>i2,v.push_back(i2);
        while(m--){
            cin>>a>>b>>c;
            v2[b]++;
            v3[a].push_back({b,c});
        }
        for(i=n;i--;){
            for(v1.push_back(i);!v1.empty();){
                i2=v1.back();
                v1.pop_back();
                if(!v2[i2]--){//neu cac node truoc da xong
                    vd[i2]+=v[i2];
                    for(auto i:v3[i2]){
                        if(vd[i[0]]<(i[1]+=vd[i2])){
                            v4[i[0]]=(v4[i2]==-2?-2:i2);
                            vd[i[0]]=i[1];
                        }else if(vd[i[0]]==i[1])v4[i[0]]=-2;
                        v1.push_back(i[0]);
                    }
                }
            }
        }
        i=max_element(vd.begin(),vd.end())-vd.begin();
        cout<<vd[i];
        if(v4[i]!=-2 and count(vd.begin(),vd.end(),vd[i])){
            for(v1.push_back(i);v1.back()!=-1;v1.push_back(v4[v1.back()]));
            v1.pop_back();
            while(!v1.empty()){
                cout<<","<<v1.back();
                v1.pop_back();
            }
            cout<<"\n";
        }else cout<<",M\n";
    }
}