import java.util.*;

public class Main
{

    public static void main(String[] args)
    {
        UndirectedAdjacencyMatrixGraph<PriorityQueueNode<Double, VertexDate>, EdgeDate> graph = new UndirectedAdjacencyMatrixGraph<>(10000);
        HashMap<String, Graph<PriorityQueueNode<Double, VertexDate>, EdgeDate>.Vertex> verticesMap = new HashMap<>();

        try (Scanner in = new Scanner(System.in))
        {
            int n = in.nextInt();
            int j = 0;

            for (int i = 0; i < n; i++)
            {
                String command = in.next();

                if (command.equals("ADD"))
                {
                    String vertexName = in.next();
                    Double vertexPenalty = in.nextDouble();
                    PriorityQueueNode<Double, VertexDate> newVertex = new PriorityQueueNode<>(Double.MAX_VALUE, new VertexDate(vertexName, vertexPenalty, j++));

                    verticesMap.put(vertexName, graph.insertVertex(newVertex));
                }
                else if (command.equals("CONNECT"))
                {
                    Graph<PriorityQueueNode<Double, VertexDate>, EdgeDate>.Vertex u = verticesMap.get(in.next());
                    Graph<PriorityQueueNode<Double, VertexDate>, EdgeDate>.Vertex v = verticesMap.get(in.next());
                    Double cost = in.nextDouble() / (u.data.value.penalty + v.data.value.penalty);

                    graph.insertEdge(u, v, new EdgeDate(cost));
                }
                else if (command.equals("PRINT_MIN"))
                {
                    PrimAlgorithm prim = new PrimAlgorithm();
                    printMSTPath(prim.applyAlgorithm(graph));
                }
            }
        }
        catch (Exception e)
        {
            e.printStackTrace();
        }
    }

    private static void printMSTPath(List<Graph<PriorityQueueNode<Double, VertexDate>, EdgeDate>.Edge> list)
    {
        StringBuilder sb = new StringBuilder();
        for(Graph<PriorityQueueNode<Double, VertexDate>, EdgeDate>.Edge edge : list)
        {
            sb.append(edge.endPoint1.data.value.name).append(":").append(edge.endPoint2.data.value.name).append(" ");
        }
        System.out.println(sb);
    }
}

class PrimAlgorithm
{
    private final MinPriorityQueue<Double, VertexDate> queue;
    private final HashMap<Graph<PriorityQueueNode<Double, VertexDate>, EdgeDate>.Vertex, Graph<PriorityQueueNode<Double, VertexDate>, EdgeDate>.Edge> vertexEdgeMap;

    public PrimAlgorithm()
    {
        vertexEdgeMap = new HashMap<>();
        this.queue = new MinPriorityQueue<>();
    }

    public List<Graph<PriorityQueueNode<Double, VertexDate>, EdgeDate>.Edge> applyAlgorithm(UndirectedAdjacencyMatrixGraph<PriorityQueueNode<Double, VertexDate>, EdgeDate> graph) throws Exception
    {
        //List for inserting in queue
        List<PriorityQueueNode<Double, VertexDate>> vertexList = new ArrayList<>(graph.vertices.size());
        for (Graph<PriorityQueueNode<Double, VertexDate>, EdgeDate>.Vertex ver : graph.vertices)
        {
            //I reassign this value because if it not the first applying of algorithm it wil be different from default value
            ver.data.key = Double.MAX_VALUE;
            vertexList.add(ver.data);
        }


        queue.union(vertexList);

        List<Graph<PriorityQueueNode<Double, VertexDate>, EdgeDate>.Edge> ans = new ArrayList<>();

        while (queue.size != 0)
        {
            //Достаем элемент с наименьшим расстоянием
            PriorityQueueNode<Double, VertexDate> startVertex = queue.extractMin();

            //Adding a new edge to the answer
            if (vertexEdgeMap.get(graph.vertices.get(startVertex.value.positionInGraphList)) != null)
                ans.add(vertexEdgeMap.get(graph.vertices.get(startVertex.value.positionInGraphList)));

            List<Pair<Graph<PriorityQueueNode<Double, VertexDate>, EdgeDate>.Vertex, Graph<PriorityQueueNode<Double, VertexDate>, EdgeDate>.Edge>> adjacentVertices = graph.getAdjacentVertices(graph.vertices.get(startVertex.value.positionInGraphList));

            for (Pair<Graph<PriorityQueueNode<Double, VertexDate>, EdgeDate>.Vertex, Graph<PriorityQueueNode<Double, VertexDate>, EdgeDate>.Edge> adjacentVertex : adjacentVertices)
            {
                Graph<PriorityQueueNode<Double, VertexDate>, EdgeDate>.Edge connectingEdge = graph.getEdge(graph.vertices.get(startVertex.value.positionInGraphList), adjacentVertex.getFirst());
                Double minCost = queue.get(adjacentVertex.getFirst().data.positionInQueueList).key;

                //Рассматриваем только те вершины, которые находятся в куче
                if (minCost != null)
                {
                    if (connectingEdge.data.cost.compareTo(minCost) < 0)
                    {
                        //Transforming adjacentVertex to node of priority queue
                        PriorityQueueNode<Double, VertexDate> consideringNode = adjacentVertex.getFirst().data;
                        queue.decreaseKey(consideringNode, connectingEdge.data.cost);
                        vertexEdgeMap.put(adjacentVertex.getFirst(), connectingEdge);
                    }
                }

            }
        }

        return ans;
    }
}

class UndirectedAdjacencyMatrixGraph<V, E> extends Graph<V, E>
{
    private final int capacityOfMatrix;
    ArrayList<ArrayList<Graph<V, E>.Edge>> adjacencyMatrix;

    public UndirectedAdjacencyMatrixGraph(int initialCapacityOfAdjacencyMatrix)
    {
        vertices = new ArrayList<>();
        edges = new ArrayList<>();
        capacityOfMatrix = initialCapacityOfAdjacencyMatrix;
        adjacencyMatrix = new ArrayList<>(initialCapacityOfAdjacencyMatrix);
    }

    @Override
    public Graph<V, E>.Vertex insertVertex(V v)
    {
        Vertex newVertex = new Vertex(v, vertices.size());
        vertices.add(newVertex);
        return newVertex;
    }

    @Override
    public Graph<V, E>.Edge insertEdge(Vertex u, Vertex v, E w)
    {
        Edge newEdge = new Edge(u, v, w, edges.size());
        edges.add(newEdge);

        if (u.positionInGraphList >= adjacencyMatrix.size())
        {
            int n = u.positionInGraphList - adjacencyMatrix.size();
            for (int i = 0; i < n + 1; i++)
                adjacencyMatrix.add(new ArrayList<>(capacityOfMatrix));
        }

        if (v.positionInGraphList >= adjacencyMatrix.size())
        {
            int n = v.positionInGraphList - adjacencyMatrix.size();
            for (int i = 0; i < n + 1; i++)
                adjacencyMatrix.add(new ArrayList<>(capacityOfMatrix));
        }

        if (v.positionInGraphList >= adjacencyMatrix.get(u.positionInGraphList).size())
        {
            int n = v.positionInGraphList - adjacencyMatrix.get(u.positionInGraphList).size();
            for (int i = 0; i <= n; i++)
                adjacencyMatrix.get(u.positionInGraphList).add(null);
        }

        adjacencyMatrix.get(u.positionInGraphList).set(v.positionInGraphList, newEdge);

        if (u.positionInGraphList >= adjacencyMatrix.get(v.positionInGraphList).size())
        {
            int n = u.positionInGraphList - adjacencyMatrix.get(v.positionInGraphList).size();
            for (int i = 0; i <= n; i++)
                adjacencyMatrix.get(v.positionInGraphList).add(null);
        }

        adjacencyMatrix.get(v.positionInGraphList).set(u.positionInGraphList, newEdge);

        return newEdge;
    }

    //TODO Needed to be checked
    @Override
    public List<Pair<Vertex, Edge>> getAdjacentVertices(Vertex vertex)
    {
        if (vertex.positionInGraphList < adjacencyMatrix.size())
        {
            List<Pair<Vertex, Edge>> list = new ArrayList<>();
            for (Edge edge : adjacencyMatrix.get(vertex.positionInGraphList))
            {
                if (edge != null)
                {
                    if (!edge.endPoint1.equals(vertex))
                        list.add(new Pair<>(edge.endPoint1, edge));
                    else list.add(new Pair<>(edge.endPoint2, edge));
                }
            }
            return list;
        }
        return new ArrayList<>();
    }

    //TODO
    @Override
    public void removeVertex(Vertex v)
    {

    }

    //TODO
    @Override
    public void removeEdge(Edge e)
    {

    }

    //TODO
    @Override
    public boolean areAdjacent(Vertex v, Vertex u)
    {
        return false;
    }

    //TODO
    @Override
    public boolean areAdjacent(Edge v, Edge u)
    {
        return false;
    }

    //TODO
    @Override
    public int degree(Vertex v)
    {
        return 0;
    }

    @Override
    public Graph<V, E>.Edge getEdge(Graph<V, E>.Vertex u, Graph<V, E>.Vertex v)
    {
        if (adjacencyMatrix.size() > v.positionInGraphList)
        {
            if (adjacencyMatrix.get(v.positionInGraphList) != null)
            {
                if (adjacencyMatrix.get(v.positionInGraphList).size() > u.positionInGraphList)
                    return adjacencyMatrix.get(v.positionInGraphList).get(u.positionInGraphList);
            }
        }
        return null;
    }
}

class EdgeDate
{
    public Double cost;

    public EdgeDate(Double cost)
    {
        this.cost = cost;
    }

    @Override
    public String toString()
    {
        return "EdgeDate{" +
                "cost=" + cost +
                '}';
    }
}

class VertexDate implements Comparable<VertexDate>
{
    public String name;
    public Double penalty;
    public int positionInGraphList;

    public VertexDate(String name, Double penalty, int positionInGraphList)
    {
        this.name = name;
        this.penalty = penalty;
        this.positionInGraphList = positionInGraphList;
    }

    @Override
    public int compareTo(VertexDate o)
    {
        return name.compareTo(o.name);
    }

    @Override
    public boolean equals(Object obj)
    {
        if (obj instanceof VertexDate)
        {
            return name.equals(((VertexDate) obj).name);
        }
        else return super.equals(obj);
    }

    @Override
    public String toString()
    {
        return "VertexDate{" +
                "name='" + name + '\'' +
                ", penalty=" + penalty +
                '}';
    }
}

class MinPriorityQueue<Key extends Comparable<Key>, Value extends Comparable<Value>> implements IPriorityQueue<Key, Value>
{
    protected final List<PriorityQueueNode<Key, Value>> list;
    private final int max_size = 100000 + 10;
    protected int size = 0;

    public MinPriorityQueue()
    {
        this.list = new ArrayList<>(max_size);
        for (int i = 0; i < max_size; i++)
            list.add(null);
    }

    private int getIndexOfParent(int index)
    {
        return (index - 1) / 2;
    }

    private int getIndexOfLeftChild(int index)
    {
        return 2 * index + 1;
    }

    private int getIndexOfRight(int index)
    {
        return 2 * index + 2;
    }

    private void heapify(int index)
    {
        //There are no checks before calling the methods, because the corresponding checks will be called in the methods themselves.
        if (size > index)
        {
            swim(index);
            sink(index);
        }
    }

    private void swim(int index)
    {
        while (index != 0 && list.get(index).compareTo(list.get(getIndexOfParent(index))) < 0)
        {
            PriorityQueueNode.swapPositions(list.get(index), list.get(getIndexOfParent(index)));
            Collections.swap(list, index, getIndexOfParent(index));
            index = getIndexOfParent(index);
        }
    }

    private void sink(int index)
    {
        for (; ; )
        {
            int l = getIndexOfLeftChild(index);
            int r = getIndexOfRight(index);

            int smallest = index;

            if (l < size && list.get(l).compareTo(list.get(smallest)) < 0)
            {
                smallest = l;
            }

            if (r < size && list.get(r).compareTo(list.get(smallest)) < 0)
            {
                smallest = r;
            }

            if (smallest != index)
            {
                PriorityQueueNode.swapPositions(list.get(index), list.get(smallest));
                Collections.swap(list, index, smallest);
                index = smallest;
            }
            else break;
        }
    }

    @Override
    public void insert(PriorityQueueNode<Key, Value> item) throws Exception
    {
        if (size == max_size)
            throw new Exception("PriorityQueue is full");

        //most likely item has an incorrect "position in list"
        item.positionInQueueList = size;
        list.set(item.positionInQueueList, item);
        size++;

        heapify(size - 1);
    }

    @Override
    public PriorityQueueNode<Key, Value> findMin()
    {
        return list.get(0);
    }

    @Override
    public PriorityQueueNode<Key, Value> extractMin() throws Exception
    {
        if (size == 0)
            throw new Exception("Heap is empty");

        PriorityQueueNode<Key, Value> min = list.get(0);

        delete(list.get(0));

        return min;
    }

    @Override
    public void decreaseKey(PriorityQueueNode<Key, Value> item, Key newKey)
    {
        if (list.get(item.positionInQueueList).compareTo(item) == 0)
        {
            item.key = newKey;
            heapify(item.positionInQueueList);
        }
    }

    @Override
    public void delete(PriorityQueueNode<Key, Value> item)
    {
        size--;
        //If there are elements but root
        if (size != 0)
        {
            int index = item.positionInQueueList;
            //swapping an extracted root and the last element
            Collections.swap(list, item.positionInQueueList, size);
            PriorityQueueNode.swapPositions(list.get(item.positionInQueueList), list.get(size));
            heapify(index);
        }
    }

    @Override
    public void union(MinPriorityQueue<Key, Value> anotherQueue)
    {
        union(anotherQueue.list);
    }

    //Optimized addition of elements from another list
    @Override
    public void union(List<PriorityQueueNode<Key, Value>> anotherList)
    {
        for (int i = 0; i < anotherList.size(); i++, size++)
            list.set(size, anotherList.get(i));

        int indexOfLastNonLeaf = getIndexOfParent(size - 1);

        //New items in list have incorrect field "position in list"
        for (int i = size - 1; i >= size - anotherList.size(); i--)
            list.get(i).positionInQueueList = i;

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

    @Override
    public PriorityQueueNode<Key, Value> get(int positionInQueueList)
    {
        return list.get(positionInQueueList);
    }
}

class PriorityQueueNode<Key extends Comparable<Key>, Value extends Comparable<Value>> implements Comparable<PriorityQueueNode<Key, Value>>
{
    public Key key;
    public Value value;
    public int positionInQueueList;

    public PriorityQueueNode(Key key, Value value)
    {
        this.key = key;
        this.value = value;
        this.positionInQueueList = -1;
    }

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

    @Override
    public int compareTo(PriorityQueueNode<Key, Value> o)
    {
        int res = this.key.compareTo(o.key);

        if (res != 0)
            return res;
        else return this.value.compareTo(o.value);
    }

    @Override
    public boolean equals(Object obj)
    {
        if (obj instanceof PriorityQueueNode<?, ?>)
        {
            return this.key.equals(((PriorityQueueNode<?, ?>) obj).key) && this.value.equals(((PriorityQueueNode<?, ?>) obj).value);
        }
        else return super.equals(obj);
    }

    public static void swapPositions(PriorityQueueNode<?, ?> a, PriorityQueueNode<?, ?> b)
    {
        int temp = a.positionInQueueList;
        a.positionInQueueList = b.positionInQueueList;
        b.positionInQueueList = temp;
    }
}

abstract class Graph<VertexDataType, EdgeDataType>
{
    protected List<Vertex> vertices;
    protected List<Edge> edges;

    abstract public Vertex insertVertex(VertexDataType vertexDataType);

    abstract public Edge insertEdge(Vertex u, Vertex v, EdgeDataType w);

    public abstract List<Pair<Vertex, Edge>> getAdjacentVertices(Vertex vertex);

    abstract public void removeVertex(Vertex v);

    abstract public void removeEdge(Edge e);

    abstract public boolean areAdjacent(Vertex v, Vertex u);

    abstract public boolean areAdjacent(Edge v, Edge u);

    abstract public int degree(Vertex v);

    abstract public Edge getEdge(Vertex u, Vertex v);

    class Vertex
    {
        public VertexDataType data;
        public int positionInGraphList;

        public Vertex(VertexDataType data, int positionInGraphList)
        {
            this.data = data;
            this.positionInGraphList = positionInGraphList;
        }
    }

    class Edge
    {
        public Vertex endPoint1;
        public Vertex endPoint2;
        public EdgeDataType data;
        public int positionInList;

        public Edge(Vertex endPoint1, Vertex endPoint2, EdgeDataType data, int positionInList)
        {
            this.endPoint1 = endPoint1;
            this.endPoint2 = endPoint2;
            this.data = data;
            this.positionInList = positionInList;
        }
    }
}

class Pair<K, V>
{
    private K first;

    public K getFirst()
    {
        return first;
    }

    private V second;

    public V getSecond()
    {
        return second;
    }

    public Pair(K first, V second)
    {
        this.first = first;
        this.second = second;
    }

    public String toString()
    {
        return first + "=" + second;
    }
}

interface IPriorityQueue<Key extends Comparable<Key>, Value extends Comparable<Value>>
{
    void insert(PriorityQueueNode<Key, Value> item) throws Exception;

    PriorityQueueNode<Key, Value> findMin();

    PriorityQueueNode<Key, Value> extractMin() throws Exception;

    void decreaseKey(PriorityQueueNode<Key, Value> item, Key newKey);

    void delete(PriorityQueueNode<Key, Value> item);

    void union(MinPriorityQueue<Key, Value> anotherQueue);

    void union(List<PriorityQueueNode<Key, Value>> anotherList);

    PriorityQueueNode<Key, Value> get(int positionInQueueList);
}