
//-------------------------------------------------------------
// Dijkstra's Algorithm
//   O(E log E)
//
// Need customization for
//   + infinite state space
//   + goal predicate
//   + path computation
//   + 1-to-all shortest distance
//
// Verified by
//   - Codeforces 77 Div1 C
//-------------------------------------------------------------

template<typename T>
class IdGen
{
	map<T, int> v2id_;
	vector<T>   id2v_;
public:
	int v2id(const T& v) {
		if( !v2id_.count(v) ) { v2id_[v] = size(); id2v_.push_back(v); }
		return v2id_[v];
	}
	const T& id2v(int i) const { return id2v_[i]; }
	int size() const { return id2v_.size(); }
};

template<typename Vert, typename Cost>
class Dijkstra
{
	IdGen<Vert> idgen;

	typedef pair<Cost,int> Edge;
	typedef vector<Edge>   Edges;
	typedef vector<Edges>  Graph;
	Graph G;

public:
	void addEdge( Vert s_, Vert t_, Cost c )
	{
		int s = idgen.v2id(s_), t = idgen.v2id(t_);
		if( max(s,t) >= G.size() ) G.resize(max(s,t)+1);
		G[s].push_back(Edge(c, t));
	}

	Cost calc( Vert s_, Vert t_ )
	{
		int s = idgen.v2id(s_), t = idgen.v2id(t_);
		if( max(s,t) >= G.size() ) G.resize(max(s,t)+1);

		priority_queue< Edge, vector<Edge>, greater<Edge> > Q;
		Q.push( Edge(0,s) );
		vector<bool> visited(G.size());
		while( !Q.empty() )
		{
			int  v = Q.top().second;
			Cost c = Q.top().first;
			Q.pop();
			if( visited[v] )
				continue;
			visited[v] = true;

			if( v == t )
				return c;

			for(int i=0; i<G[v].size(); ++i)
				if( !visited[G[v][i].second] )
					Q.push( make_pair(G[v][i].first+c, G[v][i].second) );
		}
		return -1;
	}
};
