void prim()
{
    int min=-INF;
    memset(dis,44,sizeof(dis));
    dis[1]=0,used[1]=true;
    for (int r=ed[1];r;r=next[r])
      dis[e[r]]=v[r],update[e[r]]=1;
    for (int i=1;i<n;i++)
    {
        int best=INF,r;
        for (int j=1;j<=n;j++)
          if (!used[j]&&dis[j]<best)
            best=dis[j],r=j;
        if (dis[r]>min)
          min=dis[r];
        used[r]=true;
        for (int j=ed[r];j;j=next[j])
          if (!used[e[j]])
            if (dis[e[j]]>v[j])
              dis[e[j]]=v[j],update[e[j]]=r;
    }
    printf("%d\n",min);
    printf("%d\n",n-1);
    for (int i=2;i<=n;i++)
      printf("%d %d\n",update[i],i);
}