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();
		}
	}
}