#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")

#define fi first
#define se second
#define ll long long
#define dl double

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class K, class V>
class node{
public:
        K key;
        V val = 0;
        int degree = -1;
        node<K, V>* child = nullptr;
        bool mark = false;
        node<K, V>* p = nullptr;
        node<K, V>* left = nullptr;
        node<K, V>* right = nullptr;
};

template<class K, class V>
class PriorityQueue{

public:
        int length = 0;
        node<K, V>* min = nullptr;
        node<K, V>* left = nullptr;
        node<K, V>* right = nullptr;


        void insert(K key, V value)
        {
                length++;
                auto nEl = new node<K, V>;
                nEl->val = value;
                nEl->key = key;
                nEl->left = nEl;
                nEl->right = nEl;
                nEl->degree = 0;
                PriorityQueue<K, V> nW;
                nW.min = nEl;
                nW.left = nEl;
                nW.right = nEl;
                unio(nW);
        }

        node<K, V> findMin()
        {
                return *min;
        }

        node<K, V> extractMin()
        {
                length--;
                node<K, V> res = *min;
                if(min->left == min && min->degree == 0){
                        min = nullptr;
                        left = nullptr;
                        right = nullptr;
                        return res;
                }
                auto L = min->left;
                auto R = min->right;
                auto y = min->child;
                if(min->left == min){
                        min = nullptr;
                        left = nullptr;
                        right = nullptr;
                }else{
                        if(length == 1){
                                left = min->left;
                                right = min->left;
                                right->left = right;
                                right->right = right;
                                left = right;
                                min = right;
                        }else{
                                L->right = R;
                                R->left = L;
                                left = R;
                                right = L;
                                min = left;
                        }
                }
                vector<node<K, V>*> v;
                for(int i = 0; i < res.degree; i++){
                        v.push_back(y);
                        y = y->right;
                        length++;
                }
                for(auto &x : v){
                        delete x->p;
                        x->p = nullptr;
                        x->left = x;
                        x->right = x;
                        PriorityQueue<K, V> nW;
                        nW.min = x;
                        nW.left = x;
                        nW.right = x;
                        unio(nW);
                }
                consilidate();
                return res;
        }

        void consilidate()
        {
                assert(min != nullptr);
                int l = 30;
                vector<node<K, V>*> d(l, nullptr);
                auto x = min;
                int cnt = length;
                for(int i = 0; i < cnt; i++){
                        while(d[x->degree] != nullptr && d[x->degree] != x){
                                auto F = x;
                                auto S = d[x->degree];
                                if(F->val > S->val || (F->val == S->val && F->key > S->key)){
                                        swap(F, S);
                                }
                                length--;
                                auto L = S->left;
                                auto R = S->right;
                                assert(L != S && R != S);
                                L->right = R;
                                R->left = L;
                                S->p = F;
                                if(F->child == nullptr){
                                        S->left = S;
                                        S->right = S;
                                        F->child = S;
                                }else{
                                        if(F->degree == 1){
                                                S->left = F->child;
                                                S->right = F->child;
                                                F->child->left = S;
                                                F->child->right = S;
                                                F->child = S;
                                        }else{
                                                S->left = F->child;
                                                S->right = F->child->right;
                                                F->child->right->left = S;
                                                F->child->right = S;
                                                F->child = S;
                                        }
                                }
                                d[x->degree] = nullptr;
                                F->degree += 1;
                                left = F;
                                right = F->left;
                                min = F;
                                x = F;
                        }
                        d[x->degree] = x;
                        x = x->right;
                }
                x = left;
                for(int i = 0; i < length; i++){
                        if(i == 0 || ((min->val > x->val) || (min->val == x->val && min->key > x->key))){
                                min = x;
                        }
                        x = x->right;
                }
        }

        void unio(PriorityQueue<K,V> anotherQueue)
        {
                if(min == nullptr || (anotherQueue.min->val < min->val ||
                                      (anotherQueue.min->val == min->val && anotherQueue.min->key < min->key))){
                        min = anotherQueue.min;
                }
                if(right == nullptr){
                        left = anotherQueue.left;
                        right = anotherQueue.right;
                        return;
                }
                if(left == right){
                        anotherQueue.left->left = right;
                        anotherQueue.right->right = left;
                        left->right = anotherQueue.left;
                        left->left = anotherQueue.right;
                        right = anotherQueue.right;
                        return;
                }
                anotherQueue.left->left = right;
                anotherQueue.right->right = left;
                assert(left->left == right);
                right->right = anotherQueue.left;
                anotherQueue.left->left = right;
                left->left = anotherQueue.right;
                anotherQueue.right->right = left;
                right = anotherQueue.right;

        }

        bool empty()
        {
                return (length == 0);
        }

};

template<class V, class E>
class Vertex{
public:
        int id;
        E penalty;
};

template<class V, class E>
class Edge{
public:
        Vertex<V, E> from;
        Vertex<V, E> to;
        E w;
};

template<class V, class E>
class IGraph {
        virtual Vertex<V, E> insertVertex(V& v, E& w) = 0;
        virtual void insertEdge(Vertex<V, E>& from, Vertex<V, E>& to, E& w) = 0;
        //virtual void removeVertex(Vertex<V, E> v) = 0;
        //virtual void removeEdge(Edge<V, E> e) = 0;
        //virtual bool areAdjacent(Vertex<V, E> v, Vertex<V, E> u) = 0;
        virtual int degree(Vertex<V, E> &v) = 0;
};

template<class V, class E>
class DynamicGraph : public IGraph<V, E> {
public:
        int N;
        vector<vector<E>> ed;
        vector<vector<pair<E,int>>> v;
        vector<int> degre,del;
        vector<V> g;
        map<V, int> m;
        int G = 0;

        DynamicGraph()
        {
                N = 0;
                int F = 3500;
                degre.resize(F);
                del.resize(F);
                ed.resize(F);
                g.resize(F);
               // v.resize(F);
                for(int i = 0; i < F; i++){
                        ed[i].resize(F);
                }
                for(int i = 0; i < F; i++){
                        for(int j = 0; j < F; j++){
                                ed[i][j] = -1;
                        }
                }
        }

        int degree(Vertex<V, E>& v)override
        {
                return degre[v.id];
        }

        Vertex<V, E> insertVertex(V& v, E& w)override
        {
                Vertex<V, E> nv;
                if(m.find(v) == m.end()){
                        m[v] = G++;
                }
                if(m[v] == static_cast<int>(degre.size())){
                        int len = static_cast<int>(degre.size()) + 1;
                        degre.push_back(0);
                        g.push_back("");
                        E x;
                        x = -1;
                        //this->v.push_back({});
                        for(int i = 0; i < len - 1; i++){
                                ed[i].push_back(x);
                        }
                        ed.push_back(vector<E> (len, -1));
                }
                N++;
                nv.id = m[v];
                nv.penalty = w;
                g[nv.id] = v;
                return nv;
        }

        void insertEdge(Vertex<V, E>& from, Vertex<V, E>& to, E& w)override
        {
                E W = w / (from.penalty + to.penalty);
                //v[from.id].push_back({w, to.id});
                //v[to.id].push_back({w, from.id});
                degre[from.id]++;
                degre[to.id]++;
                ed[from.id][to.id] = W;
                ed[to.id][from.id] = W;
                //return nw;
        }

        /*bool areAdjacent(Vertex<V, E> v, Vertex<V, E> u)override
        {
                return (ed[v.id][u.id] != -1);
        }

        void removeVertex(Vertex<V, E> v)override
        {
                del[v.id] = 1;
                for(int i = 0; i < N; i++){
                        if(!del[i] && i != v.id && ed[i][v.id] != -1){
                                removeEdge(ed[i][v.id]);
                        }
                }
        }

        void removeEdge(Edge<V, E> e)override
        {
                ed[e.from.id][e.to.id].w = -1;
                ed[e.from.id][e.to.id].w = -1;
        }*/
};

template<class V, class E>
class Prim{
public:
        DynamicGraph<V, E> g;
        void mst()
        {
                vector<E> D(g.N, 1e9);
                //for(int i = 0; i < g.N; i++){
                //        D[i] = 1e9;
                //}
                vector<int> par(g.N, -1);
                vector<bool> vis(g.N, false);
                for(int i = 0; i < g.N; i++){
                        if(vis[i])continue;
                        priority_queue<pair<E, int>> q;
                        D[i] = 0;
                        vis[i] = true;
                        q.push(make_pair(0, i));
                        while(!q.empty()){
                                auto w = -q.top().first;
                                auto v = q.top().second;
                                q.pop();
                                if(D[v] < w)continue;
                                if(par[v] != -1){
                                        cout << g.g[par[v]] << ":" << g.g[v] << " ";
                                        vis[v] = true;
                                }
                                int cur = 0;
                                for(int j = 0; j < g.N && cur < g.degre[v]; j++){
                                        if(vis[j])continue;
                                        if(g.ed[v][j] != -1){
                                                cur++;
                                                if(D[j] > g.ed[v][j]){
                                                        D[j] = g.ed[v][j];
                                                        q.push({-D[j], j});
                                                        par[j] = v;
                                                }
                                        }
                                }
                        }
                }
                cout << "\n";
        }
};

int main()
{
        ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        //freopen( "input.txt" , "r" , stdin );
        //freopen( "output.txt" , "w" , stdout );

        int n;
        cin >> n;
        Prim<string, float> v;
        map<string, Vertex<string, float>> m;
        for(int i = 1; i <= n; i++){
                string s;
                cin >> s;
                if(s == "ADD"){
                        string ve;
                        float penalty;
                        cin >> ve >> penalty;
                        Vertex<string, float> n_x = v.g.insertVertex(ve, penalty);
                        m[ve] = n_x;
                }else if(s == "CONNECT"){
                        string V,U;
                        float w;
                        cin >> V >> U >> w;
                        v.g.insertEdge(m[V], m[U], w);
                }else{
                        v.mst();
                }
        }
}