import java.io.*;
import java.util.Date;
import java.util.Random;

class IO
{
  public static int readInt() 
  // Reads an int from standard input.
  {
    String input = "";
    try 
    {
      BufferedReader bufRead = new BufferedReader
        (new InputStreamReader (System.in));
      input = bufRead.readLine();
    } 
    catch (java.io.IOException e) 
    {
      System.out.print("Error while reading input line!\n");
    }
    return Integer.valueOf(input).intValue();
  }
} 

class Clock 
{
  static long now()
  // returns the current time in miliseconds
  {
    return (new Date()).getTime();
  }
}

class Sort
{
  static private   final int SHORT_BOUND = 20;
  static protected final Random random = new Random(Clock.now());

  static public void sort(int[] a, int l, int h)
  // Sort h - l + 1 elements of a[] running from l to h
  {
    if (h > l) // At least two elements
      if (h - l < SHORT_BOUND) 
      {
        int i;
        int x = l;
        for (i = l + 1; i < h; i++)
          if (a[i] > a[x])
            x = i;
        if (a[x] > a[h])
        {
          i = a[x]; a[x] = a[h]; a[h] = i;
        }
        for (int r = h - 1; r >= l; r--)
        {
          x = a[r];
          for (i = r; x > a[i + 1]; i++)
            a[i] = a[i + 1];
          a[i] = x;
        }
      }
      else
      {
        int s = a[l + random.nextInt(h - l + 1)];
        int low = l; 
        int hgh = h;

        // Splitting
        while (low < hgh) 
        {
          while (low <= h && a[low] < s)
            low++;
          while (hgh >= l && a[hgh] > s)
            hgh--;
          if (low <= hgh) // swap a[low] and a[hgh]
          {
            int x = a[low]; a[low] = a[hgh]; a[hgh] = x; 
            low++;
            hgh--;
          } 
        }

        // Recursion
        sort(a, l, hgh);
        sort(a, low, h);
      }
  }

  static public void sort(int[] a, int b[], int l, int h)
  // Sort h - l + 1 elements of a[] running from l to h
  // Also rearrange the associated data in b
  {
    if (h > l) // At least two elements
      if (h - l < SHORT_BOUND) 
      {
        int i;
        int x = l;
        for (i = l + 1; i < h; i++)
          if (a[i] > a[x])
            x = i;
        if (a[x] > a[h])
        {
          i = a[x]; a[x] = a[h]; a[h] = i;
          i = b[x]; b[x] = b[h]; b[h] = i;
        }
        for (int r = h - 1; r >= l; r--)
        {
              x = a[r];
          int y = b[r];
          for (i = r; x > a[i + 1]; i++)
          {
            a[i] = a[i + 1];
            b[i] = b[i + 1];
          }
          a[i] = x;
          b[i] = y;
        }
      }
      else
      {
        int s = a[l + random.nextInt(h - l + 1)];
        int low = l; 
        int hgh = h;

        // Splitting
        while (low < hgh) 
        {
          while (low <= h && a[low] < s)
            low++;
          while (hgh >= l && a[hgh] > s)
            hgh--;
          if (low <= hgh) // swap a[low] and a[hgh]
          {
            int x;
            x = a[low]; a[low] = a[hgh]; a[hgh] = x; 
            x = b[low]; b[low] = b[hgh]; b[hgh] = x; 
            low++;
            hgh--;
          } 
        }

        // Recursion
        sort(a, b, l, hgh);
        sort(a, b, low, h);
      }
  }

  static public void sort(int[] a, int b[], int c[], int l, int h)
  // Sort h - l + 1 elements of a[] running from l to h
  // Also rearrange the associated data in b and c
  {
    if (h > l) // At least two elements
      if (h - l < SHORT_BOUND) 
      {
        int i;
        int x = l;
        for (i = l + 1; i < h; i++)
          if (a[i] > a[x])
            x = i;
        if (a[x] > a[h])
        {
          i = a[x]; a[x] = a[h]; a[h] = i;
          i = b[x]; b[x] = b[h]; b[h] = i;
          i = c[x]; c[x] = c[h]; c[h] = i;
        }
        for (int r = h - 1; r >= l; r--)
        {
              x = a[r];
          int y = b[r];
          int z = c[r];
          for (i = r; x > a[i + 1]; i++)
          {
            a[i] = a[i + 1];
            b[i] = b[i + 1];
            c[i] = c[i + 1];
          }
          a[i] = x;
          b[i] = y;
          c[i] = z;
        }
      }
      else
      {
        int s = a[l + random.nextInt(h - l + 1)];
        int low = l; 
        int hgh = h;

        // Splitting
        while (low < hgh) 
        {
          while (low <= h && a[low] < s)
            low++;
          while (hgh >= l && a[hgh] > s)
            hgh--;
          if (low <= hgh) // swap a[low] and a[hgh]
          {
            int x;
            x = a[low]; a[low] = a[hgh]; a[hgh] = x; 
            x = b[low]; b[low] = b[hgh]; b[hgh] = x; 
            x = c[low]; c[low] = c[hgh]; c[hgh] = x; 
            low++;
            hgh--;
          } 
        }

        // Recursion
        sort(a, b, c, l, hgh);
        sort(a, b, c, low, h);
      }
  }
}

class BasicHeap
{
  protected int   N;   // Maximum number of entries
  protected int[] key; // Key values
  protected int[] ind; // Index values
  protected int   n;   // Actual number of entries
  protected int   c;   // Counter

  public BasicHeap(int N)
  {
    this.N = N;
    key    = new int[N];
    ind    = new int[N];
    n      = 0;
    c      = 0;
  }

  private void percolateUp(int i)
  {
    c++;
    int j = (i - 1) / 2;
    if (j >= 0 && key[i] < key[j])
    { int 
      k = key[j]; key[j] = key[i]; key[i] = k;
      k = ind[j]; ind[j] = ind[i]; ind[i] = k;
      percolateUp(j);
    }
  }

  private void percolateDown(int i)
  {
    c++;
    int j = i;
    int l = 2 * i + 1;
    int k = l + 2;
    if (k > n)
      k = n;
    while (l < k)
    {
      if (key[2 * l] < key[2 * j])
        j = l;
      l++;
    }
    if (j != i)
    { 
      k = key[j]; key[j] = key[i]; key[i] = k;
      k = ind[j]; ind[j] = ind[i]; ind[i] = k;
      percolateDown(j);
    }
  }

  public void insert(int y, int x)
  {
    key[n] = x;
    ind[n] = y;
    percolateUp(n);
    n++;
  }

  protected void deleteMin()
  {
    n--;
    key[0] = key[n];
    ind[0] = ind[n];
    percolateDown(0);
  }

  public int deleteMinKey()
  {
    int x = key[0];
    deleteMin();
    return x;
  }

  public int deleteMinInd()
  {
    int x = ind[0];
    deleteMin();
    return x;
  }

  public boolean isEmpty()
  {
    return n == 0;
  }

  public boolean isNotEmpty()
  {
    return n > 0;
  }

  public int findMinKey()
  {
    if (n == 0)
      return Integer.MAX_VALUE;
    return key[0];
  }

  public int findMinInd()
  {
    if (n == 0)
      return -1;
    return ind[0];
  }

  public int getPercolates()
  {
    return c;
  }

  public void print()
  {
    System.out.println();
    System.out.println("Printing all nodes:");
    for (int i = 0; i < n; i++)
      System.out.println("Node[" + i + "] = (" + 
        ind[i] + ", " + key[i] + ")");
  }
}

class BinaryHeap extends BasicHeap
{
  protected int[] pos; // Positions in heap of elements

  public BinaryHeap(int N)
  {
    super(N);
    pos = new int[N];
  }

  public BinaryHeap(int[] x, int N)
  {
    this(N);
    n = N;
    for (int i = 0; i < N; i++)
    {
      key[i] = x[i];
      ind[i] = i;
      pos[i] = i;
    }
    buildHeap();
  }

  public BinaryHeap(int x, int N)
  {
    this(N);
    n = N;
    for (int i = 0; i < n; i++)
    {
      key[i] = x;
      ind[i] = i;
      pos[i] = i;
    }
  }

  protected void percolateUp(int i)
  {
    c++;
    int j = (i - 1) / 2;
    if (j >= 0 && key[i] < key[j])
    {
      int
      k = key[j]; key[j] = key[i]; key[i] = k;
      k = ind[j]; ind[j] = ind[i]; ind[i] = k;
      pos[ind[i]] = i; pos[ind[j]] = j;
      percolateUp(j);
    }
  }

  protected void percolateDown(int i)
  {
    c++;
    int j = i;
    int l = 2 * i + 1;
    int k = l + 2;
    if (k > n)
      k = n;
    while (l < k)
    {
      if (key[l] < key[j])
        j = l;
      l++;
    }
    if (j != i)
    { 
      k = key[j]; key[j] = key[i]; key[i] = k;
      k = ind[j]; ind[j] = ind[i]; ind[i] = k;
      pos[ind[i]] = i; pos[ind[j]] = j;
      percolateDown(j);
    }
  }

  public void insert(int i, int x)
  {
    key[n] = x;
    ind[n] = i;
    pos[i] = n;
    n++;
    percolateUp(n - 1);
  }

  protected void buildHeap()
  {
    for (int i = (n >> 1) - 1; i >= 0; i--)
      percolateDown(i);
  }

  protected void deleteMin()
  {
    n--;
    key[0] = key[n];
    ind[0] = ind[n];
    pos[ind[0]] = 0;
    percolateDown(0);
  }

  public void decreaseKey(int i, int x)
  {
    key[pos[i]] = x;
    percolateUp(pos[i]);
  }

  public void increaseKey(int i, int x)
  {
    key[pos[i]] = x;
    percolateDown(pos[i]);
  }

  public int keyValue(int i)
  {
    return key[pos[i]];
  }

  public boolean inQueue(int i)
  {
    return pos[i] < n && ind[pos[i]] == i;
  }

  public void print()
  {
    System.out.println();
    System.out.println("Printing all nodes:");
    for (int i = 0; i < n; i++)
      System.out.println("Node[" + i + "] = (" + ind[i] + ", " + 
        key[i] + ", " + pos[ind[i]] + ")");
  }
}

class UndirectedWeightedGraph
{
  static protected final Random random = new Random(Clock.now());

  protected int   n;
  protected int   m;
  protected int[] f;    // Starting indices 
  protected int[] srce; // Node at begining of edge 
  protected int[] targ; // Node at end      of edge 
  protected int[] wght; // Weight           of edge

  UndirectedWeightedGraph()
  {
  }

  UndirectedWeightedGraph(int n0, int m0, int l, int h)
  // Generate an undirected weighted random graph with m0 
  // undirected edges, which lead to 2 * m0 entries in the  
  // adjacency lists.
  {
    n = n0; 
    m = m0; 
    f    = new int[n + 1];
    srce = new int[2 * m];
    targ = new int[2 * m];
    wght = new int[2 * m];

    // Generate edges
    for (int i = 0; i < m; i++) 
    {
      srce[i] = random.nextInt(n);
      do
        targ[i] = random.nextInt(n);
      while (targ[i] == srce[i]);
    }

    // Set f[]-values
    Sort.sort(srce, targ, 0, m - 1); 
    f[0] = 0;
    for (int u = 0; u < n; u++) 
    {
      int j = f[u];
      while (j < m && srce[j] == u)
        j++;
      f[u + 1] = j; 
    }
    for (int u = 0; u < n; u++) 
      Sort.sort(targ, f[u], f[u + 1] - 1);

    // Remove multiple edges.
    int k = 0;
    for (int u = 0; u < n; u++)
    {
      int k0 = k;
      if (f[u] < f[u + 1])
      {
        srce[k] = srce[f[u]];
        targ[k] = targ[f[u]];
        k++;
        for (int j = f[u] + 1; j < f[u + 1]; j++)
          if (targ[j] != targ[j - 1])
          {
            srce[k] = srce[j];
            targ[k] = targ[j];
            k++;
          }
      }
      f[u] = k0;
    }
    m = k;
    f[n] = m;
    System.out.println("\nm reduced to " + m);

    // Create weights and double all edges
    for (int u = 0; u < n; u++) 
      for (int j = f[u]; j < f[u + 1]; j++)
      {
        srce[j + m] = targ[j];
        targ[j + m] = srce[j];
        wght[j + m] = wght[j] = l + random.nextInt(h - l + 1);
      }
    m = 2 * m;

    // Set f[]-values
    Sort.sort(srce, targ, wght, 0, m - 1); 
    f[0] = 0;
    for (int u = 0; u < n; u++) 
    {
      int j = f[u];
      while (j < m && srce[j] == u)
        j++;
      f[u + 1] = j; 
    }
    for (int u = 0; u < n; u++) 
      Sort.sort(targ, wght, f[u], f[u + 1] - 1);
  }

  public void print()
  {
    System.out.println();
    for (int i = 0; i < n; i++)
    {
      System.out.print("node " + i + " -> ");
      for (int j = f[i]; j < f[i + 1]; j++)
        System.out.print("(" + targ[j] + ", " + wght[j] + ") ");
      System.out.println();
    }
  }

  public int sumWeight(int c, int[] edge)
  {
    int w = 0;
    for (int i = 0; i < c; i++)
      w += wght[edge[i]];
    return w; 
  }

  void weightSort()
  {
    for (int i = 0; i < n; i++)
      Sort.sort(wght, targ, f[i], f[i + 1] - 1);
  }

  public int minWeightTree(int s, int[] edge) 
  // Prim's algorithm for computing an MST
  {
    BinaryHeap pq = new BinaryHeap(Integer.MAX_VALUE, n);
    pq.decreaseKey(s, 0);
    int counter = -1;
    int[] indx = new int[n];

    while (pq.findMinKey() < Integer.MAX_VALUE) 
    {
      int v = pq.deleteMinInd();
      if (counter >= 0)
        edge[counter] = indx[v];
      counter++;
      for (int j = f[v]; j < f[v + 1]; j++)
      {
        int w = targ[j];
        if (pq.inQueue(w) && pq.keyValue(w) > wght[j])
        {
          indx[w] = j;
          pq.decreaseKey(w, wght[j]);
        } 
      }
    } 
    System.out.println(pq.getPercolates() + " percolates");
    return counter;
  } 

  public void print(int c, int[] indx)
  // Print a list of c edges given by their indices
  {
    System.out.println();
    for (int i = 0; i < c; i++)
      System.out.println("edge[" + i + "] = (" +
        srce[indx[i]] + ", " + targ[indx[i]] + ")");
  }

}

class CompleteWeigthedGraph extends UndirectedWeightedGraph
{
  public CompleteWeigthedGraph(int n, int l, int h)
  {
    super();
    this.n = n;
    m = n * (n - 1);
    f = new int[n + 1];
    targ = new int[m];
    srce = new int[m];
    wght = new int[m];
    for (int i = 0; i < n; i++)
      f[i] = i * (n - 1);
    for (int i = 0; i < n; i++)
      for (int j = 0; j < i; j++)
      {
        targ[f[i] + j] = j;
        srce[f[i] + j] = i;
        wght[f[i] + j] = l + random.nextInt(h - l + 1);
      }
    for (int i = 0; i < n; i++)
      for (int j = i + 1; j < n; j++)
      {
        targ[f[i] + j - 1] = j;
        srce[f[i] + j - 1] = i;
        wght[f[i] + j - 1] = wght[f[j] + i];
      }
    f[n] = m;
  }
}

class PrimTest
{
  public static void main(String[] args)
  {
    System.out.print("\nGive n                       >>>   ");
    int n = IO.readInt();
    System.out.print("Complete Graph? (1 is yes)   >>>   ");
    int m = IO.readInt();
    UndirectedWeightedGraph graph;
    if (m == 1)
      graph = new CompleteWeigthedGraph(n, 1, 999999);
    else
    {
      System.out.print("Give m                       >>>   ");
      m = IO.readInt();
      graph = new UndirectedWeightedGraph(n, m, 1, 99);
    }
    if (n < 100 && m < 500)
      graph.print();

    System.out.println("\nRunning Prim's Algorithm");
    int[] edge = new int[n];
    long t = - Clock.now();
    int c = graph.minWeightTree(0, edge);
    t += Clock.now();
    int w = graph.sumWeight(c, edge);
    System.out.println("t = " + t + ", w = " + w + ", c = " + c);
    if (c < 100)
      graph.print(c, edge);

    System.out.println();
  }
}