1. 

package graphs.mst.expensiveSubway;
/**
* FWP, Ausgew├¤hlte Probleme aus dem ACM Programming Contest, WS10/11
* Problem: 11710 Expensive Subways
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=117&page=show_problem&problem=2757
*
* @author Patrick B├ędat
* @version 1.0, 14.11.2010
*
* Method : Prim
* Status : Accepted
* Runtime: 3.396
*/
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

import java.util.*;

class Main {

static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

public static void main(String[] agrs) throws IOException {
int nVerticies;
int nEdges;

do {
StringTokenizer st = new StringTokenizer(reader.readLine());
if(!st.hasMoreTokens())
break;
nVerticies = Integer.parseInt(st.nextToken());
nEdges = Integer.parseInt(st.nextToken());

if (nVerticies == 0) {
break;
}

HashMap<String, Integer> mapStationID = new HashMap<String, Integer>();
HashMap<Integer, HashSet<Edge>> neighbourEdges = new HashMap<Integer, HashSet<Edge>>();

for (int i = 0; i < nVerticies; i++) {
mapStationID.put(reader.readLine().trim(), i);
}

for (int i = 0; i < nEdges; i++) {
st = new StringTokenizer(reader.readLine());

String from = st.nextToken();
String to = st.nextToken();
int cost = Integer.parseInt(st.nextToken());

Edge e = new Edge(mapStationID.get(from), mapStationID.get(to), cost);

HashSet<Edge> neighboursFrom = neighbourEdges.get(e.from);

if (neighboursFrom == null) {
neighboursFrom = new HashSet<Edge>();
neighbourEdges.put(e.from, neighboursFrom);
}

HashSet<Edge> neighboursTo = neighbourEdges.get(e.to);

if (neighboursTo == null) {
neighboursTo = new HashSet<Edge>();
neighbourEdges.put(e.to, neighboursTo);
}

neighboursFrom.add(e);
neighboursTo.add(e);
}

//start
String startName = reader.readLine().trim();

if(!mapStationID.containsKey(startName))
{
System.out.println("Impossible");
continue;
}
int start = mapStationID.get(startName);

HashSet<Integer> newGraphVerticies = new HashSet<Integer>();
newGraphVerticies.add(start);

PriorityQueue<Edge> stack = new PriorityQueue<Edge>();

if(nVerticies == 1)
{
System.out.println("0");
continue;
}

if(neighbourEdges.get(start) == null)
{
System.out.println("Impossible");
continue;
}

for (Edge n : neighbourEdges.get(start)) {
stack.add(n);
}

int totalCost = 0;

while (newGraphVerticies.size() < nVerticies && !stack.isEmpty()) {
Edge current = stack.poll();

if (!newGraphVerticies.contains(current.from)) {
totalCost += current.cost;

for (Edge n : neighbourEdges.get(current.from)) {
if (!newGraphVerticies.contains(n.from) || !newGraphVerticies.contains(n.to)) {
stack.add(n);
}
}

newGraphVerticies.add(current.from);
} else if (!newGraphVerticies.contains(current.to)) {
totalCost += current.cost;
for (Edge n : neighbourEdges.get(current.to)) {
if (!newGraphVerticies.contains(n.from) || !newGraphVerticies.contains(n.to)) {
stack.add(n);
}
}
newGraphVerticies.add(current.to);
}
}

if (newGraphVerticies.size() < nVerticies) {
System.out.println("Impossible");
} else {
System.out.println(totalCost);
}

} while (reader.ready());
}

static class Edge implements Comparable<Edge> {

int from;
int to;
int cost;

public Edge(int from, int to, int cost) {
this.from = from;
this.to = to;
this.cost = cost;
}

public int compareTo(Edge o) {
if (cost < o.cost) {
return -1;
}
if (cost > o.cost) {
return 1;
}
return 0;
}

@Override
public int hashCode() {
return Math.min(from, to) + Math.max(from, to) * 1000;
}

@Override
public boolean equals(Object o) {
return hashCode() == o.hashCode();
}
}
}