import java.awt.Point; import java.util.*; public class f { Scanner in=new Scanner(System.in); public static void main(String[] args) { new f().go(); } private void go() { int n=in.nextInt(),m=in.nextInt(),p=in.nextInt(); ArrayList> al=new ArrayList>(); for(int i=0;i()); HashSet is=new HashSet(); for(int i=0;i mst = MST2(al,is); int ans=0; for(Point ps:mst)ans+=al.get(ps.x).get(ps.y); if(p==n){//every city is insecure...must be fully connected for(int i=1;i MST2(ArrayList> in,HashSetis){ ArrayList out=new ArrayList(); HashSet visited=new HashSet(is); final ArrayList> al=new ArrayList>(in); PriorityQueue pq=new PriorityQueue(al.size(), new Comparator(){ public int compare(Point o1, Point o2) { double d=al.get(o1.x).get(o1.y)-al.get(o2.x).get(o2.y); if(d!=0)return (int) Math.signum(d); if(o1.x!=o2.x)return o1.x-o2.x; return o1.y-o2.y; } }); int first=1; while(visited.contains(first))first++; visited.add(0); visited.add(first); if(first>=al.size())return out;//all points are insecure...no MST for(int i:in.get(first).keySet())pq.offer(new Point(first,i)); while(!pq.isEmpty()){ Point t=pq.poll(); if(visited.contains(t.y))continue; visited.add(t.y); out.add(t); for(int i:in.get(t.y).keySet()) if(!visited.contains(i))pq.offer((new Point(t.y,i))); } if(visited.size()!=al.size()){//graph is disconnected System.out.println("impossible"); System.exit(0); } return out; } }