DouKaku?

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Sample136 {
    private final Map<Graph, Integer> feeMap_ = new HashMap<Graph, Integer>();
    private final Map<Integer, List<Integer>> routeMap_ = new HashMap<Integer, List<Integer>>();

    public String[] calc(Reader reader) throws IOException {
        List<String> result = new ArrayList<String>();
        BufferedReader br = new BufferedReader(reader);
        br.readLine();    // 最初の行は読み飛ばす(エラーチェックは必要？)
        for (String line = br.readLine(); line != null; line = br.readLine()) {
            String[] values = line.split("\\s+");
            if (values[0].equals("0") && values.length == 3) {
                List<Integer> searched = searchGraph(Integer.parseInt(values[1]), Integer.parseInt(values[2]), new HashSet<Integer>());
                Collections.sort(searched);
                result.add(String.valueOf(searched.get(0)));
            } else if (values[0].equals("1") && values.length == 4) {
                addGraph(Integer.parseInt(values[1]), Integer.parseInt(values[2]), Integer.parseInt(values[3]));
            } else {
                throw new IllegalArgumentException(line);
            }
        }
        return result.toArray(new String[0]);
    }

    private void addGraph(int from, int to, int fee) {
        Graph graph = new Graph(from, to);
        Integer integer = feeMap_.get(graph);
        if (integer == null) {
            feeMap_.put(graph, fee);
        } else {
            if (integer.intValue() > fee) {
                feeMap_.put(graph, fee);
            }
        }

        addRoute(from, to);
        addRoute(to, from);
    }
    private void addRoute(int from, int to) {
        List<Integer> list = routeMap_.get(from);
        if (list == null) {
            list = new ArrayList<Integer>();
            routeMap_.put(from, list);
        }
        list.add(to);
    }

    private List<Integer> searchGraph(int from, int to, Set<Integer> searchedNodes) {
        List<Integer> result = new ArrayList<Integer>();
        List<Integer> list = routeMap_.get(from);
        if (list == null) return result;

        searchedNodes.add(from);
        searchedNodes.add(to);
        if (list.contains(to)) {
            result.add( feeMap_.get(new Graph(from, to)) );
        }
        for (int node: list) {
            if (searchedNodes.contains(node)) continue;
            List<Integer> searchResult = searchGraph(node, to, new HashSet<Integer>(searchedNodes));
            for (int search: searchResult) {
                result.add( search + feeMap_.get(new Graph(from, node)) );
            }
        }
        return result;
    }


    public static class Graph {
        public final int from;
        public final int to;

        public Graph(int from, int to) {
            if (from < to) {
                this.from = from;
                this.to = to;
            } else {
                this.from = to;
                this.to = from;
            }
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (!(obj instanceof Graph)) return false;
            Graph other = (Graph) obj;
            return this.from == other.from && this.to == other.to;
        }
        @Override
        public int hashCode() {
            return Integer.valueOf((from - 1) * 100 + (to - 1)).hashCode();
        }
    }


    public static void main(String[] args) {
        Sample136 sample = new Sample136();
        StringReader reader = new StringReader(
                "5 16\n" +
                "1 1 2 343750\n" +
                "1 1 3 3343\n" +
                "1 1 4 347392\n" +
                "1 1 5 5497\n" +
                "1 2 3 123394\n" +
                "1 2 4 545492\n" +
                "1 2 5 458\n" +
                "1 3 4 343983\n" +
                "1 3 5 843468\n" +
                "1 4 5 15934\n" +
                "0 2 1\n" +
                "0 4 1\n" +
                "0 3 2\n" +
                "0 4 2\n" +
                "0 4 3\n" +
                "0 5 3\n"
        );
        try {
            String[] result = sample.calc(reader);
            for (String line: result) {
                System.out.println(line);
            }
        } catch (IOException ex) {
            ex.printStackTrace();
        }
    }
}