CARTESIUS
Cho đồ thị vô hướng liên thông \(G_1\) gồm có \(N_1\) đỉnh được đánh số từ \(1\) đến \(N_1\) và \(M_1\) cạnh và đồ thị vô hướng liên thông \(G_2\) gồm có \(N_2\) đỉnh được đánh số từ \(1\) đến \(N_2\) đỉnh và \(M_2\) cạnh.
Đồ thị vô hướng \(G\) bao gồm \(N_1×N_2\) đỉnh, mỗi đỉnh của \(G\) có dạng \((x,y)\) sao cho \(x\) là một đỉnh thuộc \(G_1\) và \(y\) là đỉnh thuộc \(G_2\). Có \(N_1 × M_2 + N_2×M_1\) con đường hai chiều nối giữa hai đỉnh của đồ thị \(G\). con đường nối giữa hai đỉnh \((x_1,y_1 )\) và \((x_2,y_2)\) được định nghĩa như sau:
Nếu \(x_1=x_2\), và có một con đường nối giữa các đỉnh \(y_1\) và \(y_2\) của đồ thị \(G_2\). Độ dài của đường đi giữa hai đỉnh \((x_1,y_1 )\) và \((x_2,y_2)\) bằng độ dài của con đường nối giữa các đỉnh \(y_1\) và \(y_2\) trong \(G_2\)
Nếu \(y_1=y_2\), và có một con đường nối giữa đỉnh \(x_1\) và \(x_2\) của đồ thị \(G_1\). Độ dài của đường đi giữa các đỉnh \((x_1,y_1)\) và \((x_2,y_2)\) bằng độ dài đường đi giữa các thành phố \(x_1\) và \(x_2\) trong \(G_2\).
Yêu cầu: Tính độ dài của đường đi ngắn nhất từ đỉnh \((1,1)\) đến đỉnh \((N_1,N_2)\) của đồ thị \(G\).
Input
Dòng thứ nhất chứa các 2 nguyên \(N_1\) và \(M_1 (1≤N_1≤5×10^4;1≤M_1≤5×10^4)\) tương ứng là số đỉnh và số cạnh của đồ thị G_1.
\(M_1\) dòng tiếp theo mô tả các cạnh của đồ thị \(G_1\), mỗi dòng gồm ba số \(u,v,w\), tương ứng đường tri trực tiếp từ đỉnh \(u\) đến đỉnh \(v\) có trọng số \(w (1≤u,v≤N_1,1≤w≤10^7 ).\)
Dòng tiếp theo chứa các 2 nguyên \(N_2 \) và \(M_2 (1≤N_2≤5×10^4;1≤M_2≤5×10^4)\) tương ứng là số đỉnh và số cạnh của đồ thị \(G_2\).
\(M_2\) dòng tiếp theo mô tả các cạnh của đồ thị \(G_2\), mỗi dòng gồm ba số \(u,v,w\), tương ứng đường trực trực tiếp từ đỉnh \(u\) đến đỉnh \(v\) có trọng số \(w (1≤u,v≤N_2,1≤w≤10^7 ).\)
Output:
- Ghi một số nguyên là độ dài của đường đi ngắn nhất từ đỉnh \((1,1)\) đến đỉnh \((N_1,N_2)\) của đồ thị \(G\).
Ràng buộc
Subtask 1: \(n1,n2,m1,m2≤1000\)
Subtask 2: Không có ràng buộc gì thêm
Sample Input
3 2
2 1 15
3 1 14
3 2
2 1 15
3 2 15Sample Output
44
Comments