Untitled

// DFS AC (6/6) 40ms
#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

class edge{
    public:
        edge(int S,int D,int C,int A):S(S),D(D),C(C),A(A){}
        int S;
        int D;
        int C;
        int A;
};

string command;
vector<vector<edge>> M;
vector<int> min_cost(215,INT_MAX);

void add_edge(){
    int U,V,P,A;
    cin >> U >> V >> P >> A;

    bool check = false;
    for(auto &it:M[U]){
        if(it.D == V && it.A == A) {
            it.C = P;
            check = true;
            break;
        }
    }

    if(!check) M[U].push_back(edge(U,V,P,A));

    return ;
}

void delete_edge(){
    int U,V,A;
    cin >> U >> V >> A;

    for(auto it = M[U].begin();it!=M[U].end();it++){
        if(it->D == V && it->A == A) {
            M[U].erase(it--);
            break;
        }
    }

    return ;

}

int request_route(int S,int &D,int &W,int C,int A){

    if(C > W) return -1;
    if(S==D) return C;

    int ans = INT_MAX,tmp = INT_MAX;

    for(auto &i:M[S]){
        
        if(ans < C + i.C) continue;

        else if(A!=i.A && C + i.C + 5 > W) continue;
        else if(A==i.A && C + i.C > W) continue;
        else {

            int cost_change = (A==-1 || i.A==A)?0:5;
            int total_cost = C + cost_change + i.C;

            if(total_cost < min_cost[i.D]) {
                min_cost[i.D] = total_cost;
                tmp = request_route(i.D,D,W,total_cost,i.A);
            }

            if(tmp != -1) ans = min(ans,tmp);

        }
    }

    return (ans<=W)?ans:-1;
}

int main(){

    std::ios::sync_with_stdio(false);
    cin.tie(0);
    
    int C;
    cin>>C;

    M.resize(C);

    int step;
    cin>>step;

    while(step--){
        fill(min_cost.begin(),min_cost.end(),INT_MAX);
        cin>>command;
        if(command=="Add") add_edge();
        else if(command=="Delete") delete_edge();
        else {
            int S,D,W;
            cin >> S >> D >> W;
            cout << request_route(S,D,W,0,-1) << '\n';
        }
    }

    return 0;
}