72 lines
1.8 KiB
Java
72 lines
1.8 KiB
Java
import java.util.*;
|
|
|
|
class Node implements Comparable<Node> {
|
|
int node;
|
|
int dist;
|
|
|
|
Node(int node, int dist) {
|
|
this.node = node;
|
|
this.dist = dist;
|
|
}
|
|
|
|
@Override
|
|
public int compareTo(Node other) {
|
|
return this.dist - other.dist;
|
|
}
|
|
}
|
|
|
|
public class _1647_2 {
|
|
static void prim(ArrayList<ArrayList<Node>> graph, int V) {
|
|
boolean[] visited = new boolean[V+1];
|
|
PriorityQueue<Node> pq = new PriorityQueue<>();
|
|
pq.add(new Node(1, 0));
|
|
|
|
int cnt = 0, total_dist = 0, max_dist = 0;
|
|
|
|
while(!pq.isEmpty()) {
|
|
Node now = pq.poll();
|
|
int current_node = now.node, current_dist = now.dist;
|
|
|
|
if(visited[current_node]) continue;
|
|
|
|
visited[current_node] = true;
|
|
total_dist += current_dist;
|
|
max_dist = Math.max(max_dist, current_dist);
|
|
cnt += 1;
|
|
|
|
if(cnt == V) break;
|
|
|
|
for(Node next : graph.get(current_node)) {
|
|
if(!visited[next.node]) {
|
|
pq.add(next);
|
|
}
|
|
}
|
|
}
|
|
|
|
System.out.println(total_dist - max_dist);
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
Scanner sc = new Scanner(System.in);
|
|
int N = sc.nextInt(), M = sc.nextInt();
|
|
|
|
if(N==2) {
|
|
System.out.println(0);
|
|
sc.close();
|
|
return ;
|
|
}
|
|
|
|
ArrayList<ArrayList<Node>> graph = new ArrayList<>();
|
|
for(int i=0; i<=N; i++) graph.add(new ArrayList<>());
|
|
|
|
for(int i=0; i<M; i++) {
|
|
int A = sc.nextInt(), B = sc.nextInt(), C = sc.nextInt();
|
|
graph.get(A).add(new Node(B, C));
|
|
graph.get(B).add(new Node(A, C));
|
|
}
|
|
sc.close();
|
|
|
|
prim(graph, N);
|
|
}
|
|
}
|