#include <bits/stdc++.h>
#define ��R 9999
using namespace std;
int N, alk, matkat[6][6];
int** vaihtoehdot;
vector<int> satamat;
vector<int> split(const string& str, char delimiter) {
vector<int> tokens;
string token;
istringstream tokenStream(str);
while (getline(tokenStream, token, delimiter)) {
tokens.push_back(stoi(token));
}
return tokens;
}
int l�hin(int et�[], bool k�yty[]) {
int k = 0;
int min = INT_MAX;
for (int i = 0; i < N; i++) {
if (!k�yty[i] && et�[i] < min) {
min = et�[i];
k = i;
}
}
return k;
}
void init() {
for (int k = 0; k < N; k++) {
for (int j = 0; j < N; j++) {
if (k == j) {
matkat[k][j] = 0;
}
else if (matkat[k][j] == 0) {
matkat[k][j] = ��R;
}
}
}
int rivit = N, pylv��t = satamat.size();
vaihtoehdot = new int* [rivit];
if (rivit)
{
vaihtoehdot[0] = new int[rivit * pylv��t];
for (int i = 1; i < rivit; ++i)
vaihtoehdot[i] = vaihtoehdot[0] + i * pylv��t;
}
}
void laskenta(int pylv�s, int alk) {
int par[100], et�[100];
bool k�yty[100] = { 0 };
fill(et�, et� + N, INT_MAX);
alk = satamat[pylv�s];
et�[alk] = 0;
par[alk] = -1;
for (int g = 0; g < N - 1; g++) {
int u = l�hin(et�, k�yty);
k�yty[u] = true;
for (int v = 0; v < N; v++) {
if (alk == v) {
et�[v] = 0;
vaihtoehdot[v][pylv�s] = et�[v];
}
if (!k�yty[v] && (et�[u] + matkat[u][v]) < et�[v] && matkat[u][v] != 9999)
{
par[v] = u;
et�[v] = et�[u] + matkat[u][v];
vaihtoehdot[v][pylv�s] = et�[v];
}
}
}
}
void n�yt�() {
cout << "Satamat ovat ";
for (int l = 0; l < satamat.size(); l++) {
cout << satamat[l] + 1 << " ";
}
cout << endl;
cout << "Kaupunki:" << "\t\t\t";
for (int y = 0; y < satamat.size(); y++) {
cout << "Satama" << y << ":" << "\t\t\t";
}
cout << endl;
for (int t = 0; t < N; t++) {
cout << t << "\t\t\t";
for (int u = 0; u < satamat.size(); u++) {
cout << vaihtoehdot[t][u] << "\t\t\t";
}
cout << endl;
}
}
int main() {
cin >> N;
string inputString;
cin.ignore();
getline(cin, inputString);
stringstream stream(inputString);
std::vector<int> v�lisatamat;
int n;
while (stream >> n) {
v�lisatamat.push_back(n);
}
for (int z = 0; z < v�lisatamat.size(); z++) {
if (v�lisatamat[z] == 0) {
satamat.push_back(z);
}
}
int satamaM��r� = satamat.size();
int rivim��r� = N;
int laskuri = 0;
for (int i = 0; i < rivim��r� - 1; i++) {
string line;
getline(cin, line);
vector<int> rivi = split(line, ' ');
istringstream iss(line);
int num;
iss >> num;
rivi.push_back(num);
matkat[rivi[0] - 1][rivi[1] - 1] = rivi[2];
matkat[rivi[1] - 1][rivi[0] - 1] = rivi[2];
}
init();
for (int g = 0; g < satamat.size(); g++) {
laskenta(g, satamat[g]);
}
int laskin = 0;
for (int j = 0; j < N; j++) {
int pienin = ��R;
for (int i = 0; i < satamat.size(); i++) {
if (*vaihtoehdot[j, i] < pienin) {
pienin = *vaihtoehdot[j, i];
}
}
laskin += pienin;
}
cout << laskin;
}
