#include<stdio.h>
#define MAX 200000
#define TEMP 0
#define PERM 1
#define INF 0x3f3f3f3f
#include<list>
using namespace std;
#include <bits/stdc++.h>
struct node
{
int predecessor;
int dist; /*minimum distance of node from source*/
int status;
};
int adj[MAX][MAX];
int n;
list<int> the_list_for_farms = {}; // this is the list that will keep all of the verteces, with the value 1.
list<int> the_list_for_ports = {}; // this is the list that will keep all the verteces with the value 0.
void create_graph()
{
int i, amount_of_paths, starting_vertex, end_vertex, the_distance, distance_between_2_cities;
int city_identity_number;
cin >> n; // amount_of_cities; //input to see how many verteces we will have.
amount_of_paths = n - 1;
for (int k = 1; k <= n; k++) {
cin >> city_identity_number;
// city_identifier.push_back(city_identity_number);
if (city_identity_number == 1) {
the_list_for_farms.push_back(k);
}
if (city_identity_number == 0) {
the_list_for_ports.push_back(k);
}
}
// amount_of_paths = n - 1;
for (int i = 0; i < amount_of_paths; i++) {
for (int j = 0; j < 3; j++) {
cin >> distance_between_2_cities;
if (j == 0) {
starting_vertex = distance_between_2_cities;
//the_list_for_farms.insert(distance_between_2_cities)
}
if (j == 1) {
end_vertex = distance_between_2_cities;
//the_list_for_ports.insert(distance_between_2_cities)
}
if (j == 2) {
the_distance = distance_between_2_cities;
}
}
adj[starting_vertex][end_vertex] = the_distance;
adj[end_vertex][starting_vertex] = the_distance;
// cout<<adj[starting_vertex][end_vertex]<<endl;
}
/* for(int i = 0; i < MAX; i++){
for(int j = 0; j < MAX; j++){
cout<<adj[i][j]<<endl;
}
}*/
}/*End of create_graph()*/
int findpath(int s, int d, int path[MAX], int* sdist)
{
struct node state[MAX];
*sdist =0;
int i, min, count = 0, current, newdist, u, v;
// *sdist = 0;
/* Make all nodes temporary */
//cout<<n<<" This is n"<<endl;
for (i = 1; i <= n; i++)
{
state[i].predecessor = 0;
state[i].dist = INF;
state[i].status = TEMP;
}
/*Source node should be permanent*/
state[s].predecessor = 0;
state[s].dist = 0;
state[s].status = PERM;
/*Starting from source node until destination is found*/
current = s;
while (current != d)
{
for (i = 1; i <= n; i++)
{
/*Checks for adjacent temporary nodes */
if (adj[current][i] > 0 && state[i].status == TEMP)
{
newdist = state[current].dist + adj[current][i];
/*Checks for Relabeling*/
if (newdist < state[i].dist)
{
state[i].predecessor = current;
state[i].dist = newdist;
}
}
}/*End of for*/
/*Search for temporary node with minimum distand make it current node*/
min = INF;
current = 0;
for (i = 1; i <= n; i++)
{
if (state[i].status == TEMP && state[i].dist < min)
{
min = state[i].dist;
current = i;
}
}/*End of for*/
if (current == 0) /*If Source or Sink node is isolated*/
return 0;
state[current].status = PERM;
}/*End of while*/
/* Getting full path in array from destination to source */
while (current != 0)
{
count++;
path[count] = current;
current = state[current].predecessor;
}
/*Getting distance from source to destination*/
for (i = count; i > 1; i--)
{
u = path[i];
v = path[i - 1];
//*sdist += adj[u][v];
*sdist += adj[u][v];
}
return (count);
}/*End of findpath()*/
main()
{
int i, j;
int source, dest;
int path[MAX];
int count;
int minDist;
int distance;
int shortest_path = 0;
create_graph();
/* printf("The adjacency matrix is :\n");
display();
*/
for (auto i : the_list_for_farms) {
//cout<<i<<endl;
minDist = INF;
for (auto l : the_list_for_ports) {
//cout<<l<<endl;
count = findpath(i, l, path, &distance);
if(distance != 0){
if (distance < minDist){
minDist = distance;
}
}
}
shortest_path += minDist;
}
cout << shortest_path << endl;
return 0;
}/*End of main()*/