class Main {
	public static void main(String[] args) {
		Graph<WeightedEdge> g = null;
		int size = Integer.parseInt(args[1]);
		switch (args[0]) {
			case "dense" : 
				g = new DenseGraph<WeightedEdge>(size);
				break;
			case "sparse" : 
				g = new SparseGraph<WeightedEdge>(size);
				break;
		}
		String[] edges = args[2].split(",");
		for (String edge : edges) {
			String[] parts = edge.split("-|\\[|\\]");
			g.addEdge(new WeightedEdge(Integer.parseInt(parts[0]), Integer.parseInt(parts[1]), Double.parseDouble(parts[2])));
		}
		System.out.println(g.depthFirstTraversal(Integer.parseInt(args[3])));
	}
}