#ifndef __COMPRESSOR_H__
#define __COMPRESSOR_H__

/* updated: 2020-07-19 */

#include <cstdint>
#include <vector>
#include <map>
#include <functional>

/* 座標圧縮を行うクラス */
/* クラス T は比較可能である必要がある */
/* add(要素追加) -> execute(対応づけ) -> get(ID取得) という流れ */
template <class T, class Pred = std::less<T>>
class Compressor {
	using Dict = std::map<T, int32_t, Pred>;
	Dict dict_m;					// 要素 -> ID
	std::vector<T> objects_m;		// ID -> 要素

public:
	Compressor() = default;
	explicit Compressor(const Pred& pred);
	void add(const T& object);
	void execute();
	int32_t getId(const T& object) const;
	const T& getObject(int32_t id) const;
	int size() const;
};

/* 比較関数により初期化するときに用いるコンストラクタ */
template<class T, class Pred>
Compressor<T, Pred>::Compressor(const Pred& pred) 
	: dict_m(pred) {
}

/* 要素を登録する O(log n) */
template <class T, class Pred>
void Compressor<T, Pred>::add(const T& object) {
	dict_m.emplace(object, int32_t());
}

/* 各要素に座標圧縮後の ID を対応づける O(n) */
template <class T, class Pred>
void Compressor<T, Pred>::execute() {
	objects_m.reserve(dict_m.size());
	int32_t current = int32_t();
	for (auto&& pair : dict_m) {
		pair.second = current;
		objects_m.push_back(pair.first);
		++current;
	}
}

/* 各要素に対応付けられた ID を得る O(log n) */
/* 存在しない場合は例外を投げる */
template <class T, class Pred>
int32_t Compressor<T, Pred>::getId(const T& object) const {
	return dict_m.at(object);
}

/* 圧縮圧縮後の ID に対応する要素を得る O(1) */
template <class T, class Pred>
const T& Compressor<T, Pred>::getObject(int32_t id) const {
	return objects_m[id];
}

/* 現在登録されている要素数を取得 */
template <class T, class Pred>
int Compressor<T, Pred>::size() const {
	return dict_m.size();
}

template <class T, class Pred>
std::vector<int32_t> compress(const std::vector<T>& arr);

/* 配列の各要素を座標圧縮した結果を返す O(n log n) */
template <class T, class Pred>
std::vector<int32_t> compress(const std::vector<T>& arr) {
	/* 要素を全て登録 */
	Compressor<T, Pred> compressor;
	for (const T& object : arr) {
		compressor.add(object);
	}
	compressor.execute();
	
	/* 各要素に対応づけられた ID を得る */
	std::vector<int32_t> ret;
	ret.reserve(arr.size());
	for (const T& object : arr) {
		int32_t id = compressor.get(object);
		ret.push_back(id);
	}
	return ret;
}

#endif

#ifndef __GRAPH_H__
#define __GRAPH_H__

/* updated: 2020-06-27 */

#include <vector>
#include <cstdint>
#include <iostream>
#include <string>
#include <sstream>

struct GraphEdge {
	int from = 0;
	int to = 0;

	GraphEdge() = default;
	explicit GraphEdge(int from, int to);
};

template <class T>
class WeightedGraph;

/* 有向グラフクラス(特に無向グラフクラスは用意せず、両方向に辺を張ることで対応する) */
class Graph {
public:
	using EdgeID = int;
	using Edge = GraphEdge;
	using List = std::vector<EdgeID>;

private:
	std::vector<List> ids_m;
 	std::vector<Edge> edges_m;

public:
	Graph() = default;
	Graph(Graph&&) = default;
	Graph(const Graph&) = default;
	Graph& operator=(Graph&&) = default;
	Graph& operator=(const Graph&) = default;

	explicit Graph(int size);

	int size() const;
	int edgeCount() const;
	void init(int new_size);
	void reserve(int edge_count);
	
	void add(int from, int to, bool directed = true);
	const List& row(int from) const;
	const Edge& getEdge(EdgeID id) const;
	const std::vector<Edge>& getEdges() const;
	EdgeID reverseEdgeOf(EdgeID id) const;

	template <class T>
	WeightedGraph<T> toWeighted(const T& weight = T(1)) const;

	std::string toString() const;
	void debug() const;
};

template<class T>
WeightedGraph <T> Graph::toWeighted(const T& weight) const {
	return WeightedGraph<T>(*this, weight);
}

Graph inputGraph(int size, int edge_count, bool directed = true, bool one_based = true, std::istream& ist = std::cin);
Graph inputTree(int size, bool one_based = true, std::istream& ist = std::cin);
void outputGraph(const Graph& graph, bool directed = true, bool one_based = true, std::ostream& ost = std::cout);

template <class T>
using Weights = std::vector<T>;

template <class T>
class WeightedGraph {
	Graph graph_m;
	Weights<T> weights_m;

public:
	WeightedGraph() = default;
	WeightedGraph(WeightedGraph&&) = default;
	WeightedGraph(const WeightedGraph&) = default;
	WeightedGraph& operator=(WeightedGraph&&) = default;
	WeightedGraph& operator=(const WeightedGraph&) = default;

	explicit WeightedGraph(int size);
	explicit WeightedGraph(const Graph& graph, const T& weight = T(1));
	explicit WeightedGraph(const Graph& graph, const Weights<T>& weights);

	void init(int new_size);
	void reserve(int edge_count);

	void add(int from, int to, T&& weight, bool directed = true);
	void add(int from, int to, const T& weight, bool directed = true);

	const Graph& getGraph() const;
	const Weights<T>& getWeights() const;

	std::string toString() const;
	void debug() const;
};

template<class T>
WeightedGraph<T>::WeightedGraph(int size) 
	: graph_m(size) {
}

template<class T>
WeightedGraph<T>::WeightedGraph(const Graph& graph, const T& weight)
	: graph_m(graph), weights_m(graph.edgeCount(), weight) {
}

template<class T>
WeightedGraph<T>::WeightedGraph(const Graph& graph, const Weights<T>& weights) 
	: graph_m(graph), weights_m(weights) {
	assert(graph.edgeCount() == weights.size());
}

template<class T>
void WeightedGraph<T>::init(int new_size) {
	graph_m.init(new_size);
}

template<class T>
void WeightedGraph<T>::reserve(int edge_count) {
	graph_m.reserve(edge_count);
	weights_m.reserve(edge_count);
}

template<class T>
void WeightedGraph<T>::add(int from, int to, T&& weight, bool directed) {
	if (!directed) {
		add(from, to, std::move(weight), true);
		add(to, from, std::move(weight), true);
		return;
	}

	graph_m.add(from, to);
	weights_m.push_back(std::move(weight));
}

template<class T>
void WeightedGraph<T>::add(int from, int to, const T& weight, bool directed) {
	if (!directed) {
		add(from, to, weight, true);
		add(to, from, weight, true);
		return;
	}

	graph_m.add(from, to);
	weights_m.push_back(weight);
}

template<class T>
const Graph& WeightedGraph<T>::getGraph() const {
	return graph_m;
}

template<class T>
const Weights<T>& WeightedGraph<T>::getWeights() const {
	return weights_m;
}

template<class T>
std::string WeightedGraph<T>::toString() const {
	std::ostringstream stream;
	for (int from = 0; from < graph_m.size(); ++from) {
		stream << from << ": [";
		for (auto id : graph_m.row(from)) {
			const auto& edge = graph_m.getEdge(id);
			int to = edge.to;
			stream << ' ' << to << '(' << weights_m[id] << ')';
		}
		stream << " ]" << std::endl;
	}
	return stream.str();
}

template<class T>
void WeightedGraph<T>::debug() const {
	std::cerr << toString() << std::endl;
}

template <class T>
WeightedGraph<T> inputWeightedGraph(int size, int edge_count, bool directed = true, bool one_based = true, std::istream& ist = std::cin);
template <class T>
WeightedGraph<T> inputWeightedTree(int size, bool one_based = true, std::istream& ist = std::cin);
template <class T>
void outputWeightedGraph(const WeightedGraph<T>& wgraph, bool directed = true, bool one_based = true, std::ostream& ost = std::cout);

template <class T>
WeightedGraph<T> inputWeightedGraph(int size, int edge_count, bool directed, bool one_based, std::istream& ist) {
	WeightedGraph<T> ret(size);
	for (int j = 0; j < edge_count; ++j) {
		int a, b;
		T weight;
		ist >> a >> b >> weight;
		if (one_based) {
			--a; --b;
		}

		if (directed) {
			ret.add(a, b, weight);
		} else {
			ret.add(a, b, weight);
			ret.add(b, a, weight);
		}
	}
	return ret;
}

template<class T>
WeightedGraph<T> inputWeightedTree(int size, bool one_based, std::istream& ist) {
	return inputWeightedGraph<T>(size, size - 1, false, one_based, ist);
}

template<class T>
void outputWeightedGraph(const WeightedGraph<T>& wgraph, bool directed, bool one_based, std::ostream& ost) {
	const Graph& graph = wgraph.getGraph();
	const Weights<T>& weights = wgraph.getWeights();
	if (directed) {
		/* 有向グラフとみなして出力 */
		ost << graph.size() << ' ' << graph.edgeCount() << std::endl;
		for (Graph::EdgeID id = 0; id < graph.edgeCount(); ++id) {
			const auto& edge = graph.getEdge(id);
			int from = edge.from;
			int to = edge.to;
			if (one_based) {
				++from;
				++to;
			}
			ost << from << ' ' << to << ' ' << weights[id] << std::endl;
		}
	} else {
		/* 無向グラフとみなして出力(無向グラフでなかった場合の保証はない) */
		ost << graph.size() << ' ' << graph.edgeCount() / 2 << std::endl;

		/* 辺 (from, to) と (to, from) が交互に追加されているので片方を出力 */
		bool is_to_output = true;
		for (Graph::EdgeID id = 0; id < graph.edgeCount(); ++id) {
			const auto& edge = graph.getEdge(id);
			if (is_to_output) {
				int from = edge.from;
				int to = edge.to;
				if (from > to) {
					std::swap(from, to);
				}
				if (one_based) {
					++from;
					++to;
				}
				ost << from << ' ' << to << ' ' << weights[id] << std::endl;
			}
			is_to_output = !is_to_output;
		}
	}
}

#endif

#ifdef ONLY_MY_ENVIR
#include "Graph.h"
#endif

#include <cassert>
#include <sstream>

GraphEdge::GraphEdge(int from, int to)
	: from(from), to(to) {
}

Graph::Graph(int size) 
	: ids_m(size) {
}

int Graph::size() const {
	return ids_m.size();
}

int Graph::edgeCount() const {
	return edges_m.size();
}

void Graph::init(int new_size) {
	assert(new_size >= size());
	ids_m.resize(new_size);
}

void Graph::reserve(int edge_count) {
	edges_m.reserve(edge_count);
}

void Graph::add(int from, int to, bool directed) {
	if (!directed) {
		add(from, to, true);
		add(to, from, true);
		return;
	}

	ids_m[from].push_back(edges_m.size());
	edges_m.push_back(Edge(from, to));
}

const Graph::List& Graph::row(int from) const {
	assert(from >= 0 && from < size());
	return ids_m[from];
}

const Graph::Edge& Graph::getEdge(EdgeID id) const {
	assert(id >= 0 && id < edgeCount());
	return edges_m[id];
}

const std::vector<Graph::Edge>& Graph::getEdges() const {
	return edges_m;
}

/* 無向グラフ用: 逆辺を参照する */
Graph::EdgeID Graph::reverseEdgeOf(EdgeID id) const {
	return id ^ 0x1;
}

std::string Graph::toString() const {
	std::ostringstream stream;
	for (int from = 0; from < size(); ++from) {
		stream << from << ": [";
		for (auto id : row(from)) {
			const auto& edge = getEdge(id);
			int to = edge.to;
			stream << ' ' << to;
		}
		stream << " ]" << std::endl;
	}
	return stream.str();
}

void Graph::debug() const {
	std::cerr << toString() << std::endl;
}

Graph inputGraph(int size, int edge_count, bool directed, bool one_based, std::istream& ist) {
	Graph ret(size);
	for (int j = 0; j < edge_count; ++j) {
		int a, b;
		ist >> a >> b;
		if (one_based) {
			--a; --b;
		}

		if (directed) {
			ret.add(a, b);
		} else {
			ret.add(a, b);
			ret.add(b, a);
		}
	}
	return ret;
}

Graph inputTree(int size, bool one_based, std::istream& ist) {
	return inputGraph(size, size - 1, false, one_based, ist);
}

void outputGraph(const Graph& graph, bool directed, bool one_based, std::ostream& ost) {
	if (directed) {
		/* 有向グラフとみなして出力 */
		ost << graph.size() << ' ' << graph.edgeCount() << std::endl;
		for (const auto& edge : graph.getEdges()) {
			int from = edge.from;
			int to = edge.to;
			if (one_based) {
				++from;
				++to;
			}
			ost << from << ' ' << to << std::endl;
		}
	} else {
		/* 無向グラフとみなして出力(無向グラフでなかった場合の保証はない) */
		ost << graph.size() << ' ' << graph.edgeCount() / 2 << std::endl;
		
		/* 辺 (from, to) と (to, from) が交互に追加されているので片方を出力 */
		bool is_to_output = true;
		for (const auto& edge : graph.getEdges()) {
			if (is_to_output) {
				int from = edge.from;
				int to = edge.to;
				if (from > to) {
					std::swap(from, to);
				}
				if (one_based) {
					++from;
					++to;
				}
				ost << from << ' ' << to << std::endl;
			}
			is_to_output = !is_to_output;
		}
	}
}


#ifndef __SHORTEST_H__
#define __SHORTEST_H__

/* updated: 2020-07-24 */

#ifdef ONLY_MY_ENVIR
#include "Graph.h"
#endif

#include <vector>
#include <queue>
#include <utility>
#include <limits>
#include <algorithm>

/* 復元用の配列の中身を辺IDにするかどうか */

template <class T>
struct DijkstraResult {
	std::vector<T> distance;
	std::vector<int> previous;
};

template <class T>
struct BellmanFordResult {
	std::vector<T> distance;
	std::vector<int> previous;
	std::vector<bool> is_unbounded;		// 始点からの距離がいくらでも小さくなる(この場合 distance と previous の値は意味を持たない)
};

template <class T>
DijkstraResult<T> dijkstra(const WeightedGraph<T>& wgraph, int start, T infinity = std::numeric_limits<T>::max());
template <class T>
BellmanFordResult<T> bellmanFord(const WeightedGraph<T>& wgraph, int start, T infinity = std::numeric_limits<T>::max());
template <class T>
std::vector<std::vector<T>> warshallFloyd(const WeightedGraph<T>& wgraph, T infinity = std::numeric_limits<T>::max());
template <class T>
bool hasNegativeCycle(const WeightedGraph<T>& wgraph);

/* ダイクストラ法により単一始点最短路を求める O(m log n) */
template <class T>
DijkstraResult<T> dijkstra(const WeightedGraph<T>& wgraph, int start, T infinity) {
	struct State {
		T dist;
		int vertex;

		State(T dist, int vertex)
			: dist(dist), vertex(vertex) {
		}

		// 順序を逆転させる
		bool operator<(const State& right) const {
			return dist > right.dist;
		}
	};

	const Graph& graph = wgraph.getGraph();
	const auto& costs = wgraph.getWeights();
	const int size = graph.size();

	std::vector<T> distance(size, infinity);
	std::vector<int> previous(size, -1);

	std::priority_queue<State> que;
	distance[start] = 0;
	que.push(State(T(), start));

	while (!que.empty()) {
		const State state = que.top();
		que.pop();

		const T dist = state.dist;
		const int from = state.vertex;

		if (dist > distance[from]) continue;

		for (Graph::EdgeID id : graph.row(from)) {
			const auto& edge = graph.getEdge(id);
			const int to = edge.to;
			const T cost = costs[id];
			const T dist_new = dist + cost;

			if (dist_new >= distance[to]) continue;

			distance[to] = dist_new;
			previous[to] = from;
			que.push(State(dist_new, to));
		}
	}

	DijkstraResult<T> result;
	result.distance = std::move(distance);
	result.previous = std::move(previous);
	return result;
}


/* ベルマンフォード法により単一始点最短路を求める O(nm) */
/* 負閉路検出には別の関数を使う: hasNegativeCycle */
template <class T>
BellmanFordResult<T> bellmanFord(const WeightedGraph<T>& wgraph, int start, T infinity) {
	const Graph& graph = wgraph.getGraph();
	const auto& costs = wgraph.getWeights();
	const int size = graph.size();

	std::vector<T> distance(size, infinity);
	std::vector<int> previous(size, -1);
	std::vector<bool> is_unbounded(size, false);

	distance[start] = T();

	// 始点からの距離を更新
	auto update = [size, infinity, &graph, &costs](std::vector<T>& distance, std::vector<int>& previous) -> void {
		for (int from = 0; from < size; ++from) {
			if (distance[from] == infinity) continue;
			for (Graph::EdgeID id : graph.row(from)) {
				const auto& edge = graph.getEdge(id);
				const int to = edge.to;
				const T cost = costs[id];

				if (distance[from] + cost < distance[to]) {
					distance[to] = distance[from] + cost;
					previous[to] = from;
				}
			}
		}
	};

	// 負閉路を検出(あれば is_unbounded を true とする)
	auto detect = [size, infinity, &graph, &costs](std::vector<T>& distance, std::vector<bool>& is_unbounded) -> void {
		for (int from = 0; from < size; ++from) {
			if (distance[from] == infinity) continue;
			for (Graph::EdgeID id : graph.row(from)) {
				const auto& edge = graph.getEdge(id);
				const int to = edge.to;
				const T cost = costs[id];

				if (distance[from] + cost < distance[to]) {
					is_unbounded[from] = true;
					break;
				}
			}
		}
	};

	// 負閉路を伝搬
	auto propagate = [size, &graph](std::vector<bool>& is_unbounded) -> void {
		for (int from = 0; from < size; ++from) {
			if (!is_unbounded[from]) continue;
			for (Graph::EdgeID id : graph.row(from)) {
				const auto& edge = graph.getEdge(id);
				const int to = edge.to;
				is_unbounded[to] = true;
			}
		}
	};

	for (int z = 1; z < size; ++z) {
		update(distance, previous);
	}

	detect(distance, is_unbounded);

	for (int z = 1; z < size; ++z) {
		propagate(is_unbounded);
	}

	BellmanFordResult<T> result;
	result.distance = std::move(distance);
	result.previous = std::move(previous);
	result.is_unbounded = std::move(is_unbounded);
	return result;
}

/* ワーシャルフロイド法により全点間最短路を求める O(n^3) */
template <class T>
std::vector<std::vector<T>> warshallFloyd(const WeightedGraph<T>& wgraph, T infinity) {
	const Graph& graph = wgraph.getGraph();
	const auto& costs = wgraph.getWeights();
	const int size = graph.size();

	std::vector<std::vector<T>> distance(size, std::vector<T>(size, infinity));

	for (int i = 0; i < size; ++i) {
		distance[i][i] = 0;
	}

	for (int from = 0; from < size; ++from) {
		for (Graph::EdgeID id : graph.row(from)) {
			const auto& edge = graph.getEdge(id);
			int to = edge.to;
			T cost = costs[id];

			distance[from][to] = std::min(distance[from][to], cost);
		}
	}

	for (int k = 0; k < size; ++k) {
		for (int i = 0; i < size; ++i) {
			if (distance[i][k] == infinity) continue;
			for (int j = 0; j < size; ++j) {
				if (distance[k][j] == infinity) continue;
				distance[i][j] = std::min(distance[i][j], distance[i][k] + distance[k][j]);
			}
		}
	}

	return distance;
}

/* ベルマンフォード法により負閉路を検出 O(nm) */
template <class T>
bool hasNegativeCycle(const WeightedGraph<T>& wgraph) {
	const Graph& graph = wgraph.getGraph();
	const auto& costs = wgraph.getWeights();
	const int size = graph.size();

	std::vector<T> distance(size, T());

	auto update = [size, &graph, &costs](std::vector<T>& distance) -> bool {
		bool is_updated = false;
		for (int from = 0; from < size; ++from) {
			for (Graph::EdgeID id : graph.row(from)) {
				const auto& edge = graph.getEdge(id);
				const int to = edge.to;
				const T cost = costs[id];

				if (distance[from] + cost < distance[to]) {
					distance[to] = distance[from] + cost;
					is_updated = true;
				}
			}
		}
		return is_updated;
	};

	for (int z = 1; z < size; ++z) {
		update(distance);
	}

	// n 回目の更新で距離が変化したなら負閉路がある
	return update(distance);
}


#endif


#ifndef __GRAPH_UTIL_H__
#define __GRAPH_UTIL_H__

/* updated: 2020-07-24 */

// required: Graph

#ifdef ONLY_MY_ENVIR
#include "Graph.h"
#endif

#include <vector>

Graph createReverseGraph(const Graph& graph);
template <class T>
WeightedGraph<T> createReverseWeightedGraph(const WeightedGraph<T>& wgraph);

Graph createComplementGraph(const Graph& graph);

bool isBipartite(const Graph& graph);
std::vector<bool> colorBipartiteGraph(const Graph& graph);
bool isBipartiteSub(const Graph& graph, std::vector<bool>& coloring);

std::vector<std::vector<int>> connectedComponents(const Graph& graph);

Graph constructSubgraph(const Graph& graph, const std::vector<Graph::EdgeID>& ids);
template <class T>
WeightedGraph<T> constructWeightedSubgraph(const WeightedGraph<T>& wgraph, const std::vector<Graph::EdgeID>& ids);

std::vector<int> reconstructPath(const std::vector<int>& previous, int goal);

/* 辺の向きを逆転させた重みつきグラフを作成 O(n + m) */
template<class T>
WeightedGraph<T> createReverseWeightedGraph(const WeightedGraph<T>& wgraph) {
	const Graph& graph = wgraph.getGraph();
	const Weights<T>& weights = wgraph.getWeights();
	const int size = graph.size();
	const int edge_count = graph.edgeCount();

	WeightedGraph<T> ret(size);
	ret.reserve(edge_count);

	for (Graph::EdgeID id = 0; id < edge_count; ++id) {
		const auto& edge = graph.getEdge(id);
		ret.add(edge.to, edge.from, weights[id]);
	}
	return ret;
}

/* 辺IDのリストから部分グラフを構築(重み付き, 頂点は変更しない) O(n + m) */
template <class T>
WeightedGraph<T> constructWeightedSubgraph(const WeightedGraph<T>& wgraph, const std::vector<Graph::EdgeID>& ids) {
	const Graph& graph = wgraph.getGraph();
	const Weights<T>& weights = wgraph.getWeights();

	WeightedGraph<T> ret(graph.size());
	for (Graph::EdgeID id : ids) {
		const auto& edge = graph.getEdge(id);
		int from = edge.from;
		int to = edge.to;
		const T& weight = weights[id];
		ret.add(from, to, weight);
		ret.add(to, from, weight);
	}
	return ret;
}

#endif

#ifdef ONLY_MY_ENVIR
#include "GraphUtil.h"
#endif

#include <cassert>
#include <stack>
#include <algorithm>

/* 辺の向きを逆転させたグラフを作成 O(n + m) */
Graph createReverseGraph(const Graph& graph) {
	const int size = graph.size();
	Graph ret(size);
	ret.reserve(graph.edgeCount());

	for (const auto& edge : graph.getEdges()) {
		ret.add(edge.to, edge.from);
	}
	return ret;
}

/* TODO: 無向グラフは？ */
/* 補グラフを作成 O(n^2 + m) */
Graph createComplementGraph(const Graph& graph) {
	const int size = graph.size();
	std::vector<std::vector<bool>> matrix(size, std::vector<bool>(size, true));
	for (int i = 0; i < size; ++i) {
		matrix[i][i] = false;
	}

	for (const auto& edge : graph.getEdges()) {
		matrix[edge.to][edge.from] = false;
	}

	Graph ret(size);
	for (int i = 0; i < size; ++i) {
		for (int j = 0; j < size; ++j) {
			if (matrix[i][j]) {
				ret.add(i, j);
			}
		}
	}
	return ret;
}

/* 無向グラフの二部グラフ判定 O(n + m) */
bool isBipartite(const Graph& graph) {
	std::vector<bool> coloring(graph.size());
	return isBipartiteSub(graph, coloring);
}

/* 二部グラフとなるような頂点の分割を一つ見つける O(n + m) */
/* out: 頂点 -> 組 { 0, 1 } */
std::vector<bool> colorBipartiteGraph(const Graph& graph) {
	std::vector<bool> coloring(graph.size());
	bool succeeded = isBipartiteSub(graph, coloring);
	assert(succeeded);
	return coloring;
}

/* out: (bool, coloring) = (二部グラフかどうか, 二部グラフのときの塗り分け) */
bool isBipartiteSub(const Graph& graph, std::vector<bool>& coloring) {
	assert(graph.size() == coloring.size());

	struct State {
		int vertex;
		bool color;
		State(int vertex, bool color)
			: vertex(vertex), color(color) {
		}
	};

	const int size = graph.size();
	std::vector<bool> visited(size);
	for (int from = 0; from < size; ++from) {
		if (visited[from]) continue;

		std::stack<State> stack;
		stack.push(State(from, false));
		while (!stack.empty()) {
			const State state = stack.top();
			stack.pop();

			int from = state.vertex;
			bool color = state.color;
			if (visited[from]) {
				if (coloring[from] != color) return false;
				continue;
			}

			visited[from] = true;
			coloring[from] = color;

			for (auto id : graph.row(from)) {
				const auto& edge = graph.getEdge(id);
				int to = edge.to;
				stack.push(State(to, !color));
			}
		}
	}
	return true;
}

/* 連結成分分解 O(n + m) */
/* out: [各連結成分の頂点リスト] のリスト */
std::vector<std::vector<int>> connectedComponents(const Graph& graph) {
	std::vector<std::vector<int>> groups;

	const int size = graph.size();
	std::vector<bool> visited(size);
	
	auto search = [&graph, &visited](int start, std::vector<int>& group) -> void {
		std::stack<int> stack;
		stack.push(start);
		while (!stack.empty()) {
			int from = stack.top();
			stack.pop();

			if (visited[from]) continue;
			visited[from] = true;
			group.push_back(from);

			for (auto id : graph.row(from)) {
				const auto& edge = graph.getEdge(id);
				int to = edge.to;
				stack.push(to);
			}
		}
	};

	for (int from = 0; from < size; ++from) {
		if (visited[from]) continue;

		std::vector<int> group;
		search(from, group);
		groups.push_back(std::move(group));
	}

	return groups;
}

/* 辺IDのリストから部分グラフを構築(頂点は変更しない), O(n + m) */
Graph constructSubgraph(const Graph& graph, const std::vector<Graph::EdgeID>& ids) {
	Graph ret(graph.size());
	for (Graph::EdgeID id : ids) {
		const auto& edge = graph.getEdge(id);
		int from = edge.from;
		int to = edge.to;
		ret.add(from, to);
		ret.add(to, from);
	}
	return ret;
}

/* previous の配列からパスを復元 */
std::vector<int> reconstructPath(const std::vector<int>& previous, int goal) {
	std::vector<int> path;

	int curr = goal;
	while (curr != -1) {	// TODO: 始点に -1 を使うことを明文化しよう
		path.push_back(curr);
		curr = previous[curr];
	}

	std::reverse(path.begin(), path.end());
	return path;
}
#define _CRT_SECURE_NO_WARNINGS
#define _SCL_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <limits>
#include <numeric>
#include <valarray>
#include <fstream>
#include <array>
#include <random>
#include <unordered_set>
#include <unordered_map>

using namespace std;
using uint = uint32_t;
using LL = int64_t;
using ULL = uint64_t;
using PP = pair<LL, LL>;
template <typename T> using PriorityQ = priority_queue<T, vector<T>, greater<T> >;
#define REP(i, a, n) for(LL i = (a), i##_max_ = (n); i < i##_max_; ++i)
#define REM(i, a, n) for(LL i = (LL)(n) - 1, i##_min_ = (a); i >= i##_min_; --i)
#define FLOAT fixed << setprecision(16)
#define SPEEDUP { cin.tie(NULL); ios::sync_with_stdio(false); }
const int INF = 0x3FFFFFFF;
const LL INFLL = 0x3FFFFFFF3FFFFFFF;
const double INFD = 1.0e+308;
const double EPS = 1.0e-9;

void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
template <class T, class U> istream& operator>>(istream& ist, pair<T, U>& right) { return ist >> right.first >> right.second; }
template <class T, class U> ostream& operator<<(ostream& ost, const pair<T, U>& right) { return ost << right.first << ' ' << right.second; }
template <class T, class TCompatible, size_t N> void Fill(T(&dest)[N], const TCompatible& val) { fill(dest, dest + N, val); }
template <class T, class TCompatible, size_t M, size_t N> void Fill(T(&dest)[M][N], const TCompatible& val) { for (int i = 0; i < M; ++i) Fill(dest[i], val); }
template <class T> T Next() { T buf; cin >> buf; return buf; }
istream& Ignore(istream& ist) { string s; ist >> s; return ist; }
bool Inside(int i, int j, int h, int w) { return i >= 0 && i < h&& j >= 0 && j < w; }

#ifdef ONLY_MY_ENVIR
#include "Accumulator.h"
#include "Algebraic.h"
#include "BinaryMatrix.h"
#include "BinaryTree.h"
#include "Bipartite.h"
#include "BIT.h"
#include "Compressor.h"
#include "Decompositions.h"
#include "DiscreteLog.h"
#include "DynamicMod.h"
#include "Exponential.h"
#include "Factorization.h"
#include "FFT.h"
#include "FlowSolver.h"
#include "Geometric2D.h"
#include "Geometric2DFloat.h"
#include "Geometric3D.h"
#include "Geometric3DFloat.h"
#include "Graph.h"
#include "GraphUtil.h"
#include "Interpolation.h"
#include "IntMod.h"
#include "KDTree.h"
#include "LazySegmentTree.h"
#include "LIS.h"
#include "List.h"
#include "Math.h"
#include "MathUtil.h"
#include "Matrix.h"
#include "MinCostFlowSolver.h"
#include "MinMax.h"
#include "Numbers.h"
#include "Optimize.h"
#include "Permutation.h"
#include "Polynomial.h"
#include "Position.h"
#include "Random.h"
#include "Range.h"
#include "Rational.h"
#include "RollingHash.h"
#include "RuntimeMod.h"
#include "SegmentTree.h"
#include "SegmentTree2D.h"
#include "Sets.h"
#include "Shortest.h"
#include "SlidingWindow.h"
#include "SpanningTree.h"
#include "StringSearching.h"
#include "SuffixArray.h"
#include "SwitchList.h"
#include "Timer.h"
#include "Tree.h"
#include "TreeUtil.h"
#include "UnionFind.h"
#include "Util.h"
#include "VectorUtil.h"
#endif

#ifdef __GNUC__
typedef __int128 LLL;
istream& operator>>(istream& ist, __int128& val) { LL tmp; ist >> tmp; val = tmp; return ist; }
ostream& operator<<(ostream& ost, __int128 val) { LL tmp = val; ost << tmp; return ost; }
#endif

int n;
string s[50];
string t[50];
LL c[50];

bool isp(string s) {
	string t = s;
	reverse(t.begin(), t.end());
	return s == t;
}

int main() {
	cin >> n;
	REP(i, 0, n) cin >> s[i] >> c[i];
	REP(i, 0, n) {
		t[i] = s[i];
		reverse(t[i].begin(), t[i].end());
	}

	Compressor<pair<string, string>> comp;
	comp.add({ "", "" });
	REP(i, 0, n) {
		int l = s[i].size();
		REP(k, 0, l) {
			comp.add({ s[i].substr(k), "" });
			comp.add({ "", t[i].substr(k) });
		}
	}
	comp.execute();
	
	int wn = comp.size();
	WeightedGraph<LL> wg(wn);
	REP(i, 0, wn) {
		REP(k, 0, n) {
			auto p = comp.getObject(i);
			string u = p.first;
			string v = p.second;
			vector<pair<string, string>> vs;
			if (u.empty()) vs.push_back({ s[k], v });
			if (v.empty()) vs.push_back({ u, t[k] });
			
			for (auto&& q : vs) {
				string u = q.first;
				string v = q.second;
				int len = min(u.size(), v.size());
				if (u.substr(0, len) != v.substr(0, len)) continue;
				u = u.substr(len);
				v = v.substr(len);
				int j = comp.getId({ u, v });
				wg.add(i, j, c[k]);
			}
		}
	}

	LL mn = INFLL;
	REP(i, 0, n) {
		auto res = dijkstra(wg, comp.getId({ s[i], "" }), INFLL);
		if (res.distance[0] == INFLL) continue;

		auto path = reconstructPath(res.previous, 0);
		int prev = 1;
		string rec;

		for (auto id : path) {
			auto p = comp.getObject(id);
			string u = p.first;
			string v = p.second;
			
			int nprev = 0;
			if (u.empty()) nprev = 1;
			if (nprev == prev) continue;
			prev = nprev;
			rec += u + v;
		}

		LL ans = c[i] + res.distance[0];
		if (!isp(rec)) ans *= 2;
		mn = min(mn, ans);
	}
	REP(i, 0, n) {
		auto res = dijkstra(wg, comp.getId({ "", t[i] }), INFLL);
		if (res.distance[0] == INFLL) continue;

		auto path = reconstructPath(res.previous, 0);
		int prev = 0;
		string rec;

		for (auto id : path) {
			auto p = comp.getObject(id);
			string u = p.first;
			string v = p.second;

			int nprev = 0;
			if (u.empty()) nprev = 1;
			if (nprev == prev) continue;
			prev = nprev;
			rec += u + v;
		}

		LL ans = c[i] + res.distance[0];
		if (!isp(rec)) ans *= 2;
		mn = min(mn, ans);
	}
	cout << (mn == INFLL ? -1 : mn / 2) << endl;
	return 0;
}


Measured memory_bytes: 4084