#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
const int N = 4e5+5;
int n;vector<pair<int,int>> adj[N];
struct edge{
int a,b,cost;
edge(int x,int y,int z):a(x),b(y),cost(z){}
bool operator<(edge &x)const{
return cost<x.cost;
}
};
int parent[N],group[N];
struct dsu
{
dsu()
{
for(int i=0;i<N;i++)
{
parent[i]=i;
group[i]=1;
}
}
int find(int i)
{
if(parent[i]==i)
{
return i;
}
return parent[i]= find(parent[i]);
}
bool samegroup(int x,int y)
{
return find(x)==find(y);
}
void merge(int x,int y)
{
int leader1=find(x);
int leader2=find(y);
if(leader1==leader2) return;
if(group[leader1]>group[leader2]) swap(leader1,leader2);
group[leader2]+=group[leader1];
parent[leader1]=leader2;
}
int getsize(int x)
{
return group[find(x)];
}
};
bool vis[N]={};
/////////////////////////////////////////////
const int Log=23;
int mx[N][Log],anc[N][Log],level[N],s[N];vector<pair<int,int>>adj2[N];
void BuildAncestors(int node,int parent,int cost)
{
level[node]=level[parent]+1;
anc[node][0]=parent;
mx[node][0]=cost;
for(int o=1;o<Log;o++)
{
int p=anc[node][o-1];
anc[node][o]=anc[p][o-1];
mx[node][o]=max(mx[p][o-1],mx[node][o-1]);
}
for(auto it:adj2[node])
{
if(it.first==parent)
{
continue;
}
BuildAncestors(it.first,node,it.second);
}
}
int KthAncestor(int node,int k)
{
for(int o=Log-1;o>=0;o--)
{
if(k&(1<<o))
{
node=anc[node][o];
}
}
return node;
}
int MX(int node,int k)
{
int ret=0;
for(int o=Log-1;o>=0;o--)
{
if(k&(1<<o))
{
ret=max(ret,mx[node][o]);
node=anc[node][o];
}
}
return ret;
}
int LCA(int u,int v)
{
if(level[u]<level[v])
{
swap(u,v);
}
u=KthAncestor(u,level[u]-level[v]);
if(u==v)
{
return u;
}
for(int i=Log-1;i>=0;i--)
{
if(anc[u][i]!=anc[v][i])
{
u=anc[u][i];
v=anc[v][i];
}
}
return anc[u][0];
}
signed main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>n;
map<string,int>m;
int idx=1;
vector<edge>ed;
for(int i=0;i<n;i++)
{
string x,y;int c;cin>>x>>y>>c;
int a,b;
if(m.find(x)!=m.end())a=m[x];
else a=m[x]=idx++;
if(m.find(y)!=m.end())b=m[y];
else b=m[y]=idx++;
ed.push_back(edge(a,b,c));
adj[a].push_back({b,c});
adj[b].push_back({a,c});
}
sort(ed.begin(),ed.end());
dsu d;
map<pair<int,int>,bool>mp;
vector<edge>ed2,ed3;
for(int i=0;i<n;i++){
if(d.samegroup(ed[i].a,ed[i].b)){
ed3.push_back(ed[i]);
continue;
}
d.merge(ed[i].a,ed[i].b);
adj2[ed[i].a].push_back({ed[i].b,ed[i].cost});
adj2[ed[i].b].push_back({ed[i].a,ed[i].cost});
ed2.push_back(ed[i]);
}
if(d.getsize(1)!=m.size()){
cout<<-1;
return 0;
}
BuildAncestors(1,1,0);
ll ans=0;
for(auto it:ed2)
{
ans+=it.cost;
}
for(auto it:ed3)
{
int lc=LCA(it.a,it.b);
if(max(MX(it.a,level[it.a]-level[lc]),MX(it.b,level[it.b]-level[lc]))>=it.cost) ans+=it.cost;
}
cout<<ans;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiNkZWZpbmUgIGxsIGxvbmcgbG9uZwojZGVmaW5lIGludCBsb25nIGxvbmcKY29uc3QgaW50IE4gPSA0ZTUrNTsKaW50IG47dmVjdG9yPHBhaXI8aW50LGludD4+IGFkaltOXTsKCnN0cnVjdCBlZGdlewogICAgaW50IGEsYixjb3N0OwogICAgZWRnZShpbnQgeCxpbnQgeSxpbnQgeik6YSh4KSxiKHkpLGNvc3Qoeil7fQogICAgYm9vbCBvcGVyYXRvcjwoZWRnZSAmeCljb25zdHsKICAgICAgICByZXR1cm4gY29zdDx4LmNvc3Q7CiAgICB9Cn07CmludCBwYXJlbnRbTl0sZ3JvdXBbTl07CnN0cnVjdCBkc3UKewogICAgZHN1KCkKICAgIHsKICAgICAgICBmb3IoaW50IGk9MDtpPE47aSsrKQogICAgICAgIHsKICAgICAgICAgICAgcGFyZW50W2ldPWk7CiAgICAgICAgICAgIGdyb3VwW2ldPTE7CiAgICAgICAgfQogICAgfQogICAgaW50IGZpbmQoaW50IGkpCiAgICB7CiAgICAgICAgaWYocGFyZW50W2ldPT1pKQogICAgICAgIHsKICAgICAgICAgICAgcmV0dXJuIGk7CiAgICAgICAgfQogICAgICAgIHJldHVybiBwYXJlbnRbaV09IGZpbmQocGFyZW50W2ldKTsKICAgIH0KICAgIGJvb2wgc2FtZWdyb3VwKGludCB4LGludCB5KQogICAgewogICAgICAgIHJldHVybiBmaW5kKHgpPT1maW5kKHkpOwogICAgfQogICAgdm9pZCBtZXJnZShpbnQgeCxpbnQgeSkKICAgIHsKICAgICAgICBpbnQgbGVhZGVyMT1maW5kKHgpOwogICAgICAgIGludCBsZWFkZXIyPWZpbmQoeSk7CiAgICAgICAgaWYobGVhZGVyMT09bGVhZGVyMikgcmV0dXJuOwogICAgICAgIGlmKGdyb3VwW2xlYWRlcjFdPmdyb3VwW2xlYWRlcjJdKSBzd2FwKGxlYWRlcjEsbGVhZGVyMik7CiAgICAgICAgZ3JvdXBbbGVhZGVyMl0rPWdyb3VwW2xlYWRlcjFdOwogICAgICAgIHBhcmVudFtsZWFkZXIxXT1sZWFkZXIyOwogICAgfQogICAgaW50IGdldHNpemUoaW50IHgpCiAgICB7CiAgICAgICAgcmV0dXJuIGdyb3VwW2ZpbmQoeCldOwogICAgfQp9Owpib29sIHZpc1tOXT17fTsKCi8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLy8vLwpjb25zdCBpbnQgTG9nPTIzOwppbnQgbXhbTl1bTG9nXSxhbmNbTl1bTG9nXSxsZXZlbFtOXSxzW05dO3ZlY3RvcjxwYWlyPGludCxpbnQ+PmFkajJbTl07CnZvaWQgQnVpbGRBbmNlc3RvcnMoaW50IG5vZGUsaW50IHBhcmVudCxpbnQgY29zdCkKewogICAgbGV2ZWxbbm9kZV09bGV2ZWxbcGFyZW50XSsxOwogICAgYW5jW25vZGVdWzBdPXBhcmVudDsKICAgIG14W25vZGVdWzBdPWNvc3Q7CiAgICBmb3IoaW50IG89MTtvPExvZztvKyspCiAgICB7CiAgICAgICAgaW50IHA9YW5jW25vZGVdW28tMV07CiAgICAgICAgYW5jW25vZGVdW29dPWFuY1twXVtvLTFdOwogICAgICAgIG14W25vZGVdW29dPW1heChteFtwXVtvLTFdLG14W25vZGVdW28tMV0pOwogICAgfQogICAgZm9yKGF1dG8gaXQ6YWRqMltub2RlXSkKICAgIHsKICAgICAgICBpZihpdC5maXJzdD09cGFyZW50KQogICAgICAgIHsKICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgfQogICAgICAgIEJ1aWxkQW5jZXN0b3JzKGl0LmZpcnN0LG5vZGUsaXQuc2Vjb25kKTsKICAgIH0KfQppbnQgS3RoQW5jZXN0b3IoaW50IG5vZGUsaW50IGspCnsKICAgIGZvcihpbnQgbz1Mb2ctMTtvPj0wO28tLSkKICAgIHsKICAgICAgICBpZihrJigxPDxvKSkKICAgICAgICB7CiAgICAgICAgICAgIG5vZGU9YW5jW25vZGVdW29dOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBub2RlOwp9CmludCBNWChpbnQgbm9kZSxpbnQgaykKewogICAgaW50IHJldD0wOwogICAgZm9yKGludCBvPUxvZy0xO28+PTA7by0tKQogICAgewogICAgICAgIGlmKGsmKDE8PG8pKQogICAgICAgIHsKICAgICAgICAgICAgcmV0PW1heChyZXQsbXhbbm9kZV1bb10pOwogICAgICAgICAgICBub2RlPWFuY1tub2RlXVtvXTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gcmV0Owp9CmludCBMQ0EoaW50IHUsaW50IHYpCnsKICAgIGlmKGxldmVsW3VdPGxldmVsW3ZdKQogICAgewogICAgICAgIHN3YXAodSx2KTsKICAgIH0KICAgIHU9S3RoQW5jZXN0b3IodSxsZXZlbFt1XS1sZXZlbFt2XSk7CiAgICBpZih1PT12KQogICAgewogICAgICAgIHJldHVybiB1OwogICAgfQogICAgZm9yKGludCBpPUxvZy0xO2k+PTA7aS0tKQogICAgewogICAgICAgIGlmKGFuY1t1XVtpXSE9YW5jW3ZdW2ldKQogICAgICAgIHsKICAgICAgICAgICAgdT1hbmNbdV1baV07CiAgICAgICAgICAgIHY9YW5jW3ZdW2ldOwogICAgICAgIH0KICAgIH0KICAgIHJldHVybiBhbmNbdV1bMF07Cn0Kc2lnbmVkIG1haW4oKQp7CiAgICBpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApO2Npbi50aWUoMCk7Y291dC50aWUoMCk7CiAgICBjaW4+Pm47CiAgICBtYXA8c3RyaW5nLGludD5tOwogICAgaW50IGlkeD0xOwogICAgdmVjdG9yPGVkZ2U+ZWQ7CiAgICBmb3IoaW50IGk9MDtpPG47aSsrKQogICAgewogICAgICAgIHN0cmluZyB4LHk7aW50IGM7Y2luPj54Pj55Pj5jOwogICAgICAgIGludCBhLGI7CiAgICAgICAgaWYobS5maW5kKHgpIT1tLmVuZCgpKWE9bVt4XTsKICAgICAgICBlbHNlIGE9bVt4XT1pZHgrKzsKICAgICAgICBpZihtLmZpbmQoeSkhPW0uZW5kKCkpYj1tW3ldOwogICAgICAgIGVsc2UgYj1tW3ldPWlkeCsrOwogICAgICAgIGVkLnB1c2hfYmFjayhlZGdlKGEsYixjKSk7CiAgICAgICAgYWRqW2FdLnB1c2hfYmFjayh7YixjfSk7CiAgICAgICAgYWRqW2JdLnB1c2hfYmFjayh7YSxjfSk7CiAgICB9CgogICAgc29ydChlZC5iZWdpbigpLGVkLmVuZCgpKTsKICAgIGRzdSBkOwogICAgbWFwPHBhaXI8aW50LGludD4sYm9vbD5tcDsKICAgIHZlY3RvcjxlZGdlPmVkMixlZDM7CiAgICBmb3IoaW50IGk9MDtpPG47aSsrKXsKICAgICAgICBpZihkLnNhbWVncm91cChlZFtpXS5hLGVkW2ldLmIpKXsKICAgICAgICAgICAgZWQzLnB1c2hfYmFjayhlZFtpXSk7CiAgICAgICAgICAgIGNvbnRpbnVlOwogICAgICAgIH0KICAgICAgICBkLm1lcmdlKGVkW2ldLmEsZWRbaV0uYik7CiAgICAgICAgYWRqMltlZFtpXS5hXS5wdXNoX2JhY2soe2VkW2ldLmIsZWRbaV0uY29zdH0pOwogICAgICAgIGFkajJbZWRbaV0uYl0ucHVzaF9iYWNrKHtlZFtpXS5hLGVkW2ldLmNvc3R9KTsKICAgICAgICBlZDIucHVzaF9iYWNrKGVkW2ldKTsKICAgIH0KICAgIGlmKGQuZ2V0c2l6ZSgxKSE9bS5zaXplKCkpewogICAgICAgIGNvdXQ8PC0xOwogICAgICAgIHJldHVybiAwOwogICAgfQogICAgQnVpbGRBbmNlc3RvcnMoMSwxLDApOwogICAgbGwgYW5zPTA7CiAgICBmb3IoYXV0byBpdDplZDIpCiAgICB7CiAgICAgICAgYW5zKz1pdC5jb3N0OwogICAgfQogICAgZm9yKGF1dG8gaXQ6ZWQzKQogICAgewogICAgICAgIGludCBsYz1MQ0EoaXQuYSxpdC5iKTsKICAgICAgICBpZihtYXgoTVgoaXQuYSxsZXZlbFtpdC5hXS1sZXZlbFtsY10pLE1YKGl0LmIsbGV2ZWxbaXQuYl0tbGV2ZWxbbGNdKSk+PWl0LmNvc3QpIGFucys9aXQuY29zdDsKICAgIH0KICAgIGNvdXQ8PGFuczsKfQo=