class Graph {
public:
    vector<vector<int>> dist;
    int num;
    Graph(int n, vector<vector<int>>& edges) {
        num=n;
        dist=vector<vector<int>>(n,vector<int>(n,INT_MAX));//所有端点之间距离初始化为无穷大
        for (int i=0;i<n;i++) dist[i][i]=0;//自己到自己的距离为0
        int m=edges.size();
        for (int i=0;i<m;i++){
            dist[edges[i][0]][edges[i][1]]=edges[i][2]; //添加一条边，左端点到右端点的距离为cost
        }
        for (int k=0;k<n;k++){ //对于每一个端点，看它是否可以作为中间点连接另外两个端点a和b，如果比直接连接ab更近，则更新ab之间的最短距离
            for (int i=0;i<n;i++){
                for (int j=0;j<n;j++){
                    if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX){
                        dist[i][j] = min (dist[i][j], dist[i][k]+dist[k][j]);
                    }
                }
            }
        }
    }
    
    void addEdge(vector<int> edge) {
        if (edge[2]>dist[edge[0]][edge[1]]) //如果添加的边的权值大于已有最短路径权值，不需要更新dist[][]，直接返回
            return;
        for (int i=0;i<num;i++){ //对于每一对端点ij，看是否可以通过edge作为中间边连接，比直接连接ij更近，则更新ij之间的最短距离
            for (int j=0;j<num;j++){
                if (dist[i][edge[0]] != INT_MAX && dist[edge[1]][j] != INT_MAX){
                    dist[i][j] = min (dist[i][j], dist[i][edge[0]]+dist[edge[1]][j]+edge[2]);
                }
            }
        }
    }
    
    int shortestPath(int node1, int node2) {
        return dist[node1][node2]==INT_MAX?-1:dist[node1][node2];
    }
};

/**
 * Your Graph object will be instantiated and called as such:
 * Graph* obj = new Graph(n, edges);
 * obj->addEdge(edge);
 * int param_2 = obj->shortestPath(node1,node2);
 */