/*
* CTU Open 2013
* HES
*/
package template;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;
/**
*
* @author cteam007
*/
public class Fr {
}
while (!st.hasMoreTokens()) {
}
return st.nextToken();
}
return Integer.
parseInt(nextToken
()); }
/**
* @param args the command line arguments
*/
Fr instance = new Fr();
while (instance.run()) {
}
}
if (in == null) {
return false;
}
useLine(in);
int numberOfNodes = nextInt();
int centralNode = nextInt();
StartGraph sGraf = new StartGraph(numberOfNodes, centralNode);
for (int i = 0; i < numberOfNodes - 1; i++) {
int nodeOne = nextInt();
int nodeTwo = nextInt();
int valve = nextInt();
sGraf.getStartNode(nodeOne).addEdge(nodeTwo, valve);
sGraf.getStartNode(nodeTwo).addEdge(nodeOne, valve);
}
BFS.create(centralNode, sGraf);
//System.out.println("");
//sGraf.printGraph();
//System.out.println("");
System.
out.
println(sGraf.
getStartNode(sGraf.
central).
minimum(sGraf
));
return true;
}
}
class StartNode {
int id;
int parrent;
int valve;
char status;
public StartNode(int id) {
this.id = id;
this.status = 'F';
this.parrent = -1;
}
public void addEdge(int dest, int valve) {
neighbours.put(dest, valve);
}
public void addChild(int dest, int valve) {
childs.put(dest, valve);
}
public int minimum(StartGraph graph) {
int min = 0;
for (Integer integer
: childs.
keySet()) { StartNode v = graph.getStartNode(integer);
min += v.minimum(graph);
}
if (childs.isEmpty()) {
return valve;
}
return Math.
min(min, valve
); }
}
class StartGraph {
int central;
int count;
public StartGraph(int count, int central) {
this.central = central;
this.count = count;
for (int i = 1; i <= count; i++) {
nodes.put(i, new StartNode(i));
}
}
public StartNode getStartNode(int id) {
return nodes.get(id);
}
public void printGraph() {
for (int i = 0; i < count; i++) {
System.
out.
println("Node: " + nodes.
get(i
).
id + " v: " + nodes.
get(i
).
valve);
for (Integer integer
: nodes.
get(i
).
childs.
keySet()) { StartNode v = getStartNode(integer);
System.
out.
println("-->Node: " + v.
id + " v: " + v.
valve); }
}
}
}
class BFS {
public static void create(int central, StartGraph graf) {
StartNode s = graf.getStartNode(central);
s.status = 'O';
s.parrent = -1;
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(central);
while (!queue.isEmpty()) {
StartNode u = graf.getStartNode(queue.remove());
for (Integer integer
: u.
neighbours.
keySet()) { StartNode v = graf.getStartNode(integer);
if (v.status == 'F') {
u.addChild(v.id, u.neighbours.get(v.id));
v.valve = u.neighbours.get(v.id);
v.status = 'O';
v.parrent = u.id;
queue.add(v.id);
}
}
u.status = 'C';
}
}
}