#define MAXN (100005)
#define INF (1000000009)

/* graph */
int n; // number of vertexes
std::vector<std::pair<int, int>> g[MAXN]; // adjacenty lists

int d[MAXN], p[MAXN];

struct SetComparator
{
	bool operator()(int a, int b) const 
	{
        return d[a] == d[b] ? a < b : d[a] < d[b]; 
    }
};

void dijkstra(int start)
{
	for (int i = 0; i < n; i++) d[i] = INF;
	d[start] = 0;
	p[start] = -1;
	
	std::set<int, SetComparator> set;
	set.insert(start);
	
	while (!set.empty()) 
	{
		int v = *set.begin();
		set.erase(set.begin());
 
		for (auto &edge : g[v]) 
		{
			int to = edge.first, len = edge.second;
			
			if (d[v] + len < d[to]) 
			{
				set.erase(to);
				d[to] = d[v] + len;
				p[to] = v;
				set.insert(to);
			}
		}
	}
}