#include "swap.h"
#include "bits/stdc++.h"
#include <vector>
using namespace std;
using ll = long long;
const int MAXN = 1e5+5;
vector < vector< pair<ll, ll> > > adj(MAXN);
ll sum_dist = 0;
ll dist[MAXN];
int edges, max_ed = 0, u_max;
int n, m;
/*void dfs(int v, int p, ll val = 1e9)
{
for(int i = 0; i < adj[v]).size(); i++)
{
pair<ll, ll> e = adj[v][i];
if(e.second == p)
continue;
if(e == adj[v][0]) {
if(adj[v].size() > 1 && adj[v][1].second != p)
val = min(val, adj[v][1].first);
else if(adj[v].size() > 2)
val = min(val, adj[v][2].first);
}
else {
if(adj[v][0].second != p)
val = min(val, adj[v][0].first);
else if(adj[v].size() > 1)
val = min(val, adj[v][1].first);
}
dist[e.second] = dist[v] + e.first;
dfs(e, v, val);
}
dist[v] += val;
}*/
void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) {
m = M;
n = N;
for(int i = 0; i < M; i++)
{
adj[U[i]].push_back({W[i], V[i]});
adj[V[i]].push_back({W[i], V[i]});
dist[V[i]] = W[i]; // for sub 2
u_max = max(u_max, U[i]);
sum_dist += W[i];
}
for(int i = 0; i < N; i++)
{
sort(adj[i].begin(), adj[i].end());
max_ed = max(max_ed, (int)adj[i].size());
}
}
int getMinimumFuelCapacity(int X, int Y) {
if(max_ed <= 2) // Sub 1
{
if(m == n - 1)
return -1;
else
return sum_dist;
}
if(u_max == 0) // Sub 2
{
if(X > Y)
swap(X, Y);
ll sum = 0;
if(X != 0) {
sum = 2LL * (dist[X] + dist[Y]) + 2LL * ((adj[0][0].second != X && adj[0][0].second != Y) ? adj[0][0].first : ((adj[0][1].second != X && adj[0][1].second != Y) ? adj[0][1].first : (adj[0].size() > 2) ? adj[0][2].first : 0LL));
} else
{
sum = 2LL * (dist[Y] + (adj[0][0].second != Y ? adj[0][0].first + (adj[0][1].second != Y ? adj[0][1].first : adj[0][2].first): adj[0][1].first + adj[0][2].first));
}
return sum;
}
return 0;
}
