import java.io.*;
import java.util.*;

// Min-heap som brukes i Dijkstras algoritme
//
// Lagrer nodenummeret og en verdi (avstand) for noder i en heap,
// ordnet på verdi
//
// Holder også rede på hvilken indeks i heapen hver node er lagret på,
// for å kunne justere verdier (avstander)
//
public class nodeHeap
{
    // Indre klasse som brukes til å lagre en node i heapen
    //
    private class node
    {
	// Nodens nummer og verdi
	int nr, verdi;

	// Konstruktør
	public node(int n, int v)
	{
	    nr = n;
	    verdi = v;
	}
    }

    // Array som lagrer selve heapen
    private node a[];

    // Array som inneholder indeksen i heapen der hver node ligger lagret
    // Brukes til å justere verdier for noder i heapen
    // Noden med nummer x ligger lagret i a[heapIndeks[x]]
    private int heapIndeks[];

    // Indeks til sist brukte element i heap-arrayen
    private int n;

    // Maks. antall verdier i heapen
    private int maxN;
    
    // Konstruktør
    //
    public nodeHeap(int length)
    {
	maxN = length;
	a = new node[maxN];
	heapIndeks = new int[maxN];
	n = -1;
    }
	    
    // Sjekker om heap er tom
    //
    public boolean isEmpty()
    {
	return (n < 0);
    }

    // Legger inn ny node i heap 
    // Terminerer ved feil (full heap)
    //
    public void insert(int nr, int verdi)
    {
	// Øker størrelsen på heapen
	n++;

	// Heap full?
	if (n == maxN)
	{
	    System.err.println("Error: Heap full");
	    System.exit(1);
	}
	
	// Setter inn ny node sist i heapen
	a[n] = new node(nr, verdi);

	// Setter indeksen til den nye noden
	heapIndeks[nr] = n;
	
	int child = n;
	int parent = (n-1)/2;
	boolean done = false;;

	// Bytter ny verdi oppover i heap inntil den står riktig
	while (!done)
	{
	    if (child == 0)
		// Ny verdi står i roten, ferdig
		done = true;
	    else if (a[child].verdi >= a[parent].verdi)
		// Ny verdi står riktig i forhold til forelder, ferdig
		done = true;
	    else
	    {
		// Bytter om ny verdi og forelder
		node tmp= a[child];
		a[child] = a[parent];
		a[parent] = tmp;

		// Justerer indeksene der nodene er lagret
		heapIndeks[a[child].nr] = child;
		heapIndeks[a[parent].nr] = parent;

		// Finner indeks til neste foreldernode
		child = parent;
		parent = (child-1)/2;
	    }
	}
    }
    
    // Fjerner minste verdi fra heap
    // Returnerer nummeret til noden som fjernes
    // Terminerer ved feil (tom heap)
    //
    public int removeMin()
    {
	return remove(0);
    }

    // Intern metode som fjerner roten i et subtre i heapen
    //
    private int remove(int root)
    {
	// Heap tom?
	if (isEmpty())
	{
	    System.err.println("Error: Heap empty");
	    System.exit(1);
	}
	
	// Ta vare på minste verdi i roten av heap
	node min = a[root];

	// Flytt elementet bakerst i heap til roten
	a[root] = a[n];

	// Setter indeksen til den nye roten
	heapIndeks[a[root].nr] = root;

	// Reduser størrelsen på heap
	n--;

	int current = root;
	int left, right, next = 0;
	boolean done = false;
	    
	// Bytt verdien i roten nedover i heap inntil den står riktig
	while (!done)
	{
	    // Beregner indeksene til venstre og høyre barn
	    left = 2*current + 1;
	    right = left + 1;
	    
	    // Hvis indeks til venstre barn er utenfor heapen, står
	    // verdien riktig som et blad på nederste nivå
	    if (left > n)
		done = true;
	    else
	    {    
		// Hvis indeks til høyre barn er utenfor heapen, skal
		// vi sammenligne og evt. bytte plass med venstre barn
		if (right > n)
		    next = left;

		// Hvis begge barna ligger i heapen, skal vi
		// sammenligne og evt. bytte plass med barnet med
		// minst verdi
		else if (a[left].verdi < a[right].verdi)
		    next = left;
		else
		    next = right;

		// Ferdig hvis ny verdi står riktig i forhold til
		// minste barn
		done = (a[current].verdi < a[next].verdi);
	    }

	    // Hvis ikke ferdig, bytt med minste barn
	    if (!done)
	    {
		node tmp = a[next];
		a[next] = a[current];
		a[current] = tmp;

		// Justerer indeksene der nodene er lagret
		heapIndeks[a[next].nr] = next;
		heapIndeks[a[current].nr] = current;

		// Fortsett å sjekke nedover i heapen
		current = next;
	    }
	}
	// Returner nummeret til den "gamle" roten i heapen
	return min.nr;
    }

    // Endrer/justerer verdien til en node i heapen
    // Setter noden riktig i heapen igjen etter justering
    //
    public void adjust(int nr, int verdi)
    {
	// Finner hvor i heapen noden ligger
	int nrIndeks = heapIndeks[nr];

	// Fjerner denne noden fra heapen
	remove(nrIndeks);

	// Setter inn node med justert verdi på nytt i heapen
	insert(nr, verdi);
    }
}