import java.util.*;
import java.util.stream.Collectors;

public class Program {
    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            Integer number = Integer.parseInt(in.next());

            DynamicGraph<Double> graph = new DynamicGraph<>(number);
            HashMap<String, Node<Vertex<Double>>> mapV = new HashMap<>();
            ArrayList <Edge<Double, Double>> results = null;

            for (int i = 0; i < number; i++) {
                String command = in.next();
                if (command.equals("ADD")) {
                    String name = in.next();
                    Double penalty = in.nextDouble();

                    mapV.put(name, graph.insertVertex(name, penalty));
                } else if (command.equals("CONNECT")) {
                    String v = in.next();
                    String u = in.next();
                    Double cost = in.nextDouble();

                    graph.insertEdge(mapV.get(v), mapV.get(u), cost);
                } else if (command.equals("PRINT_MIN")) {

                    IPriorityQueue<Vertex<Double>, Double> priorityQueue = new BinaryHeap<>();
                    PrimAlgorithm<Double, Double> primAlgorithm = new PrimAlgorithm<Double, Double>(graph, Double.MAX_VALUE);
                    results = primAlgorithm.applyAlgorithm();
                    StringBuilder builder = new StringBuilder();
                    for (int l = 0; l < results.size(); l++) {
                        builder.append(results.get(l).vertexTo.value.name).append(":").append(results.get(l).vertexFrom.value.name).append(" ");
                        System.out.print(builder);
                        builder.setLength(0);
                    }
                    System.out.println();
                }
            }
        }
    }
}

class PrimAlgorithm<V extends Comparable<V>, E extends Comparable<E>> {
    // храним: key - вес минимамального ребра, value - вершина
    IPriorityQueue<E, Vertex<V>> priorityQueue;
    CommonDynamicGraph<V, E> graph;
    // key - вершина, оборнутая в Node(чтобы иметь быстрый доступ в priorityQueue) value - ребро, минимальное по стоимости
    HashMap<Node<Vertex<V>>, Edge<E, V>> visited;

    public <K> PrimAlgorithm(CommonDynamicGraph<V, E> graph, E CUSTOM_INF) {
        this.graph = graph;
        this.priorityQueue = new BinaryHeap<>();
        this.visited = new HashMap<>();

        //достаём все вершины с графа и помещаем их в priorityQueue с очень большим значением
        ArrayList<Node<Vertex<V>>> list = graph.vertices;
        ArrayList<Pair<E, Node<Vertex<V>>>> list2 = new ArrayList<>();
        for (Node<Vertex<V>> iterator : list)
        {
            list2.add(new Pair<>(CUSTOM_INF, iterator));
        }
        priorityQueue.union(list2);
    }

    public ArrayList <Edge<E, V>> applyAlgorithm() {
        //лист из рёбер, дающих MST
        ArrayList<Edge<E, V>> result = new ArrayList<>();

        while (priorityQueue.size() != 0) {
            //достаём элемент с наименьшим ребром
            Node<Vertex<V>> startVertex = priorityQueue.extractMin();
            //добавляем его ребро с map в ответ
            if (visited.get(startVertex) != null)
                result.add(visited.get(startVertex));

            //просим у графа все соседние вершины
            ArrayList<Node<Vertex<V>>> adjacentVertexes = graph.getAdjacentVertexes(startVertex);

            //итерируемся по ним
            for (int i = 0; i < adjacentVertexes.size(); i++) {
                Node<Vertex<V>> adjacentVertex = adjacentVertexes.get(i);

                // мы рассматриваем только те соседние вершины, что не находятся в приорити кью (так как у них уже отмечено минимальноу значение)
                E minEdge = priorityQueue.getKeyByValue(adjacentVertex);
                if (minEdge != null) {

                    // беру ребро между ними
                    Edge<E, V> newEdge = graph.getEdge(adjacentVertex, startVertex);
                    if (newEdge != null) {
                        E newCost = newEdge.cost;

                        // если это рёбро весит меньше, чем рёбро, которое соответвует этой вершине в приорити кью
                        if (newCost.compareTo(minEdge) < 0) {
                            // заменеям ключ на  newCost
                            priorityQueue.decreaseKey(adjacentVertex, newCost);
                            visited.put(adjacentVertex, newEdge);
                        }
                    }
                }
            }
        }
        return result;
    }
}


class Vertex<V> implements Comparable<Vertex<V>> {
    public String name;
    public V cost;
    public int indexVertex;

    public Vertex(String name, V cost, int index) {
        this.name = name;
        this.cost = cost;
        this.indexVertex = index;
    }

    @Override
    public int compareTo(Vertex<V> o) {
        return this.name.compareTo(o.name);
    }

    @Override
    public String toString() {
        return this.name;
    }
}

class Edge<E extends Comparable<E>, V> {
    public E cost;
    public Node<Vertex<V>> vertexFrom;
    public Node<Vertex<V>> vertexTo;
    public int index;

    public Edge(E cost, Node<Vertex<V>> vertexFrom, Node<Vertex<V>> vertexTo, int index) {
        this.cost = cost;
        this.vertexFrom = vertexFrom;
        this.vertexTo = vertexTo;
        this.index = index;
    }
}

// V - String, E - Integer
class CommonDynamicGraph<V, E extends Comparable<E>> {

    int size;
    int n;

    ArrayList<ArrayList<Edge<E, V>>> matrix;
    //список всёз вершин
    ArrayList<Node<Vertex<V>>> vertices;

    public CommonDynamicGraph(int n) {
        this.n = n;
        size = 0;
        vertices = new ArrayList<>(n);
        matrix = new ArrayList<>(n);
    }

    public ArrayList<Node<Vertex<V>>> getAdjacentVertexes(Node<Vertex<V>> v) {
        ArrayList<Node<Vertex<V>>> vertices = new ArrayList<>(n);
        if (matrix.size() > v.value.indexVertex)
            for (int i = 0; i < matrix.get(v.value.indexVertex).size(); i++) {
                if (matrix.get(v.value.indexVertex).get(i) != null)
                    vertices.add(matrix.get(v.value.indexVertex).get(i).vertexTo);
            }
        return vertices;
    }

    public Edge<E, V> getEdge(Node<Vertex<V>> v, Node<Vertex<V>> u) {
        if (matrix.get(v.value.indexVertex) != null)
            return matrix.get(v.value.indexVertex).get(u.value.indexVertex);
        else return null;
    }

    public Node<Vertex<V>> insertVertex(String name, V value) {
        Node<Vertex<V>> newVertex = new Node<Vertex<V>>(new Vertex<>(name, value, size), -1);
        size++;
        vertices.add(newVertex);
        return newVertex;
    }

    public Edge<E, V> insertEdge(Node<Vertex<V>> from, Node<Vertex<V>> to, E cost) {
        Edge<E, V> edge1 = new Edge<>(cost, from, to, -1);
        Edge<E, V> edge2 = new Edge<>(cost, to, from, -1);

        if (matrix.size() <= from.value.indexVertex || matrix.size() <= to.value.indexVertex)
            for (int i = matrix.size(); i <= Integer.max(from.value.indexVertex, to.value.indexVertex); i++)
                matrix.add(new ArrayList<>(n));

        if (from.value.indexVertex >= matrix.get(to.value.indexVertex).size() || to.value.indexVertex >= matrix.get(from.value.indexVertex).size()) {
            for (int i = matrix.size(); i < Integer.max(from.value.indexVertex, to.value.indexVertex); i++)
                matrix.get(Integer.min(from.value.indexVertex, to.value.indexVertex)).add(null);
        }

        matrix.get(from.value.indexVertex).set(to.value.indexVertex, edge1);
        matrix.get(to.value.indexVertex).set(from.value.indexVertex, edge2);
        return edge1;
    }

    public void removeVertex(V v) {

    }

    public void removeEdge(Edge<E, V> e) {

    }

    public boolean areAdjacent(Edge<E, V> v, Edge<E, V> u) {
        return false;
    }

    public boolean areAdjacent(Node<Vertex<V>> v, Node<Vertex<V>> u) {
        return false;
    }

    public int degree(Node<Vertex<V>> v) {
        return 0;
    }
}

class DynamicGraph<V extends Number> extends CommonDynamicGraph<V, Double> {
    public DynamicGraph(int n) {
        super(n);
    }

    @Override
    public Edge<Double, V> insertEdge(Node<Vertex<V>> from, Node<Vertex<V>> to, Double cost) {
        Edge<Double, V> edge1 = new Edge<>(cost / (from.value.cost.doubleValue() + to.value.cost.doubleValue()), from, to, -1);
        Edge<Double, V> edge2 = new Edge<>(cost / (from.value.cost.doubleValue() + to.value.cost.doubleValue()), to, from, -1);
        if (matrix.size() <= from.value.indexVertex || matrix.size() <= to.value.indexVertex)
            for (int i = matrix.size(); i <= Integer.max(from.value.indexVertex, to.value.indexVertex); i++)
                matrix.add(new ArrayList<>(n));

        if (from.value.indexVertex >= matrix.get(to.value.indexVertex).size())
            for (int i = 0, tempSize = from.value.indexVertex - matrix.get(to.value.indexVertex).size(); i <= tempSize; i++)
                matrix.get(to.value.indexVertex).add(null);

        if (to.value.indexVertex >= matrix.get(from.value.indexVertex).size())
            for (int i = 0, tempSize = to.value.indexVertex - matrix.get(from.value.indexVertex).size(); i <= tempSize; i++)
                matrix.get(from.value.indexVertex).add(null);

        matrix.get(from.value.indexVertex).set(to.value.indexVertex, edge1);
        matrix.get(to.value.indexVertex).set(from.value.indexVertex, edge2);
        return edge1;
    }
}


interface IPriorityQueue<K extends Comparable<K>, V extends Comparable<V>> {

    void Check();

    int size();

    void insert(K newKey, Node<V> newValue);

    Node<V> findMin();

    Node<V> extractMin();

    void decreaseKey(Node<V> node, K newKey);

    void delete(K key, V value);

    public K getKeyByValue(Node<V> value);

    void union(BinaryHeap<K, V> anotherQueue);

    void union(List<Pair<K, Node<V>>> anotherList);
}

class Node<V extends Comparable<V>> implements Comparable<Node<V>> {
    V value;
    int indexNode;

    public Node(V value, int index) {
        this.value = value;
        this.indexNode = index;
    }

    @Override
    public String toString() {
        return value.toString();
    }

    @Override
    public int compareTo(Node<V> o) {
        return this.value.compareTo(o.value);
    }
}

class BinaryHeap<K extends Comparable<K>, V extends Comparable<V>> implements IPriorityQueue<K, V> {
    int tailIndex;
    protected Pair<K, Node<V>>[] arrayHeap;

    private void heapify(int index) {
        if (arrayHeap[(index - 1) / 2].compareTo(arrayHeap[index]) > 0)
            bubbleUp(index);
            // если объект больше детей по ключу
        else
            bubbleDown(index);
    }

    @Override
    public void Check() {
        for (int i = 0; i < tailIndex; i++)
            if (arrayHeap[i].getValue().indexNode != i)
                System.out.println(i + "\n");
    }

    private void bubbleDown(int index) {
        if ((2 * index + 2) < tailIndex) {
            if (arrayHeap[index].compareTo(arrayHeap[2 * index + 1]) > 0 && arrayHeap[2 * index + 1].compareTo(arrayHeap[2 * index + 2]) <= 0) {
                swap(2 * index + 1, index);
                bubbleDown(2 * index + 1);
            } else if (arrayHeap[index].compareTo(arrayHeap[2 * index + 2]) > 0 && arrayHeap[2 * index + 1].compareTo(arrayHeap[2 * index + 2]) > 0) {
                swap(2 * index + 2, index);
                bubbleDown(2 * index + 2);
            }

        } else if ((2 * index + 1) < tailIndex) {
            if (arrayHeap[index].compareTo(arrayHeap[2 * index + 1]) > 0) {
                swap(2 * index + 1, index);
                bubbleDown(2 * index + 1);
            }
        }
    }

    private void swap(int iA, int iB) {
        Pair<K, Node<V>> temp = arrayHeap[iA];
        arrayHeap[iA] = arrayHeap[iB];
        arrayHeap[iB] = temp;

        arrayHeap[iA].getValue().indexNode = iA;
        arrayHeap[iB].getValue().indexNode = iB;
    }

    private void bubbleUp(int index) {
        // если объект меньше родителя
        int a = (index - 1) / 2, b = index;
        while (arrayHeap[a].compareTo(arrayHeap[b]) > 0) {
            swap(a, b);

            b = a;
            a = (b - 1) / 2;
        }
    }


    public BinaryHeap() {
        tailIndex = 0;
        arrayHeap = new Pair[4000 + 100];
    }

    @Override
    public K getKeyByValue(Node<V> value) {
        if (tailIndex <= value.indexNode || value.indexNode == -1)
            return null;
        else
            return arrayHeap[value.indexNode].getKey();
    }

    @Override
    public int size() {
        return tailIndex;
    }

    @Override
    public void insert(K newKey, Node<V> newValue) {
        arrayHeap[tailIndex] = new Pair<K, Node<V>>(newKey, newValue);
        newValue.indexNode = tailIndex;
        // добавляю элемент в конец, но затем мне нужно его поднять
        heapify(tailIndex);
        tailIndex++;
    }

    @Override
    public Node<V> findMin() {
        if (tailIndex != 0)
            return arrayHeap[0].getValue();
        else
            return null;
    }

    @Override
    public Node<V> extractMin() {
        if (tailIndex != 0) {
            Node<V> returnValue = arrayHeap[0].getValue();
            arrayHeap[0].getValue().indexNode = -1;
            arrayHeap[0] = arrayHeap[tailIndex - 1];
            arrayHeap[0].getValue().indexNode = 0;
            tailIndex--;
            //проверка Up and Bubble Down
            // если объект меньше родителя по ключу
            heapify(0);
            return returnValue;
        } else return null;
    }

    @Override
    public void decreaseKey(Node<V> node, K newKey) {
        if (arrayHeap[node.indexNode].getValue().compareTo(node) == 0 && tailIndex > node.indexNode) {
            arrayHeap[node.indexNode].setKey(newKey);
            heapify(node.indexNode);
        }
    }

    @Override
    public void delete(K key, V value) {

    }

    @Override
    public void union(BinaryHeap<K, V> anotherQueue) {
        union(Arrays.asList(anotherQueue.arrayHeap));
    }

    @Override
    public void union(List<Pair<K, Node<V>>> anotherList) {
        for (int i = 0; i < anotherList.size(); i++, tailIndex++) {
            arrayHeap[tailIndex] = anotherList.get(i);
            arrayHeap[tailIndex].getValue().indexNode = tailIndex;
        }

        int index = (tailIndex - 2) / 2;

        for (int i = index; i >= 0; i--)
            heapify(index);
    }
}

class Pair<K extends Comparable<K>, V extends Comparable<V>> implements Comparable<Pair<K, V>> {
    private K key;

    public K getKey() {
        return key;
    }

    public void setKey(K key) {
        this.key = key;
    }

    private V value;

    public V getValue() {
        return value;
    }

    public void setValue(V value) {
        this.value = value;
    }

    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }

    @Override
    public String toString() {
        return key + "=" + value;
    }

    @Override
    public int compareTo(Pair<K, V> o) {
        if (o.key.compareTo(this.key) == 0)
            return this.value.compareTo(o.value);
        else return this.key.compareTo(o.key);
    }
}