#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<vector>
#include<list>
#include<limits.h>
#include<algorithm>
using namespace std;

class Graph
{
class Node;
class Edge;
public:
	unordered_map<int, Node*>node;///<点集
	unordered_set<Edge*>edge;///<边集
	Graph(vector<vector<int> >a)///<假设边不会出现先重复，否则不太好写
	{
		for(auto vec:a)
		{
			int from=vec[0], to=vec[1], weight=vec[2];
			if(node.find(from)==node.end())///<如果没有from节点，就加入
				node.insert(pair<int, Node*>(from, new Node(from)));
			if(node.find(to)==node.end())///<如果没有to节点就加入
				node.insert(pair<int, Node*>(to, new Node(to)));

			auto pfrom = node.find(from)->second, pto = node.find(to)->second;///<边集中获取from和to的指针
			auto pedge = new Edge(pfrom, pto, weight);///<获取边的指针
			++pto->in;///<to的入度增加
			++pfrom->out;///<from的出度增加
			pfrom->nextnode.push_back(pto);///<from的next节点是to
			pfrom->edge.push_back(pedge);///<from连接的边是edge
			edge.insert(pedge);///<加入边级
		}
	}
	~Graph()
	{
		for(auto pedge:edge)
			delete(pedge);
		for(auto it_pair:node)
			delete(it_pair.second);
	}
private:	
	class Node
	{
	public:
		int name;//节点名称
		int in;//入度
		int out;//出度
		list<Edge*>edge;
		list<Node*>nextnode;
		Node(int _name):name(_name),in(0),out(0){};
		~Node()
		{}
	};

	class Edge
	{ 
	public:
		Node* from;///<边的起点
		Node* to;///<边的终点
		int weight;///<节点权重
		Edge(Node* _from, Node* _to, int _weight):from(_from), to(_to), weight(_weight){};
		~Edge()
		{}
	};
};

bool cmp(pair<int, int>a, pair<int,int>b)
{
	return a.second < b.second;
}
int networkDelayTime(vector<vector<int>>& times, int n, int k) {
	Graph graph(times);
	unordered_map<int, int>atainable, unatainable;
	int ret = 0;
	for(auto node_pair : graph.node)
		unatainable.insert(pair<int,int>(node_pair.first, INT_MAX));
	unatainable.find(k)->second = 0;
	while(!unatainable.empty())
	{
		auto itpair_un2a = min_element(unatainable.begin(), unatainable.end(), cmp);///<从unatainable到atainable的pair迭代器
		if(INT_MAX==itpair_un2a->second)
			break;
		atainable.insert(*itpair_un2a);
		auto list_nextnode = graph.node.find(itpair_un2a->first)->second->nextnode;///<移动节点nextnode的list
		for(auto nextnode : list_nextnode)///<每个node，是node的指针
		{
			if(atainable.end()==atainable.find(nextnode->name))
			{
				auto unatainable_it = unatainable.find(nextnode->name);
				unatainable_it->second = min(unatainable_it->second, graph.node.find(nextnode->name)->second->name+itpair_un2a->second);
			}
		}
		ret = max(ret, itpair_un2a->second);
		unatainable.erase(itpair_un2a);
	}
	return ret;
}

int main(void)
{
	vector<vector<int> >times={{2,1,1},{2,3,1},{3,4,1}};
	cout<<networkDelayTime(times, 4, 2)<<endl;
	return 0;
}