import java.util.Scanner; /** * * @author gzf19902016 */ public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { int n = scanner.nextInt(); // 道路数 int m = scanner.nextInt(); // 村庄数 if (n == 0) { break; } int[] village = new int[m + 1], villageLength = new int[m + 1]; int villageNum = 0, from, to, length; distance[] graph = new distance[n]; for (int i = 0; i < n; i++) { graph[i] = new distance(); from = scanner.nextInt(); to = scanner.nextInt(); length = scanner.nextInt(); if (i == 0) { graph[i].from = from; graph[i].to = to; graph[i].length = length; } else { int j; for (j = i - 1; j >= 0 && graph[j].length > length; j--) { graph[j + 1].from = graph[j].from; graph[j + 1].to = graph[j].to; graph[j + 1].length = graph[j].length; } graph[j + 1].from = from; graph[j + 1].to = to; graph[j + 1].length = length; } } for (int i = 0; i < n; i++) { from = graph[i].from; to = graph[i].to; if (village[from] == 0 && village[to] == 0) { //都不在,散点 village[from] = village[to] = ++villageNum; villageLength[villageNum] = graph[i].length; } else if (village[from] == 0 && village[to] != 0) { //孤点在外的情况 village[from] = village[to]; villageLength[village[to]] += graph[i].length; } else if (village[from] != 0 && village[to] == 0) { village[to] = village[from]; villageLength[village[from]] += graph[i].length; } else { if (village[from] != village[to]) { //合并组, 规则: 编号小的组合并编号大的组 int little = village[from] < village[to] ? village[from] : village[to]; int high = village[from] > village[to] ? village[from] : village[to]; for (int j = 1; j <= n; j++) if (village[j] == high) village[j] = little; villageLength[little] += (villageLength[high] + graph[i].length); villageLength[high] = 0; } } if (isAllIn(village)) break; } if (isAllIn(village)) System.out.println(villageLength[1]); else System.out.println("?"); } } private static boolean isAllIn(int[] village) { for(int i = 1; i < village.length; i++){ if(village[i] != village[1]) return false; } return true; } private static class distance { public int from; public int to; public int length; } } /************************************************************** Problem: 2204 User: admin Language: Java Result: Accepted Time:677 ms Memory:40584 kb ****************************************************************/