#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int M = N + 7;
const double EPS = 1e-10;
const int MOD = 1e9 + 7;
const long long INF = 2e18;
const long long K = 1e6;
set<pair<int, int>> g[M];
set<pair<int, pair<int, int>>> edges;
map<long long, int> p;
map<long long, long long> vals;
multiset<pair<long long, int>> threes;
pair<bool, bool> isImportant(int v, int u) {
  int w = p[v * K + u];
  auto itv = g[v].begin();
  auto itu = g[u].begin();
  bool flagv = false, flagu = false;
  for (int i = 0; i < 3; i++) {
    flagv |= v && (itv == g[v].end() || itv->first > w ||
                   (itv->first == w && u <= itv->second));
    flagu |= u && (itu == g[u].end() || itu->first > w ||
                   (itu->first == w && v <= itu->second));
    if (itv != g[v].end()) itv++;
    if (itu != g[u].end()) itu++;
  }
  return {flagv, flagu};
}
set<pair<int, int>>::iterator getThird(int v) {
  auto it = g[v].begin();
  for (int i = 0; i < min((int)g[v].size(), 2); i++, it++) {
  }
  return it;
}
long long calcSumThree(int v) {
  if ((int)g[v].size() < 3) return INF;
  auto it = g[v].begin();
  long long cur = 0;
  for (int i = 0; i < 3; i++, it++) cur += it->first;
  return vals[v] = cur;
}
void threesIns(const pair<long long, int>& x) {
  if (x.first != INF) threes.insert(x);
}
void threesErs(const pair<long long, int>& x) {
  if (x.first != INF) threes.erase(x);
}
void add(int v, int u, int w) {
  p[v * K + u] = w;
  p[u * K + v] = w;
  pair<bool, bool> imp = isImportant(v, u);
  if (imp.first && imp.second) edges.insert({w, {min(v, u), max(v, u)}});
  if (imp.first) {
    auto itv = getThird(v);
    if (itv != g[v].end() && isImportant(v, itv->second).second)
      edges.erase({itv->first, {min(v, itv->second), max(v, itv->second)}});
    threesErs({vals[v], v});
  }
  if (imp.second) {
    auto itu = getThird(u);
    if (itu != g[u].end() && isImportant(u, itu->second).second)
      edges.erase({itu->first, {min(u, itu->second), max(u, itu->second)}});
    threesErs({vals[u], u});
  }
  g[v].insert({w, u});
  g[u].insert({w, v});
  if (imp.first) threesIns({calcSumThree(v), v});
  if (imp.second) threesIns({calcSumThree(u), u});
}
void del(int v, int u) {
  int w = p[v * K + u];
  pair<bool, bool> imp = isImportant(v, u);
  g[v].erase({w, u});
  g[u].erase({w, v});
  if (imp.first && imp.second) edges.erase({w, {min(v, u), max(v, u)}});
  if (imp.first) {
    auto itv = getThird(v);
    if (itv != g[v].end() && isImportant(v, itv->second).second)
      edges.insert({itv->first, {min(v, itv->second), max(v, itv->second)}});
    threesErs({vals[v], v});
    threesIns({calcSumThree(v), v});
  }
  if (imp.second) {
    auto itu = getThird(u);
    if (itu != g[u].end() && isImportant(u, itu->second).second)
      edges.insert({itu->first, {min(u, itu->second), max(u, itu->second)}});
    threesErs({vals[u], u});
    threesIns({calcSumThree(u), u});
  }
}
void print_info(int n, ostream& os) {
  os << "----------------------------------------\n";
  os << "INFO:\n";
  os << "\nThrees:\n";
  for (auto it : threes) os << it.first << ' ' << it.second << "\n";
  os << "\nEdges:\n";
  for (auto it : edges)
    os << it.first << ' ' << it.second.first << ' ' << it.second.second << "\n";
  os << "\nGraph\n";
  for (int v = 1; v <= n; v++) {
    os << "   " << v << " | ";
    for (auto to : g[v]) {
      os << to.first << ' ' << to.second << " | ";
    }
    os << "\n";
  }
  os << "----------------------------------------\n";
}
long long calcAns() {
  int w = edges.begin()->first;
  int v = edges.begin()->second.first;
  int u = edges.begin()->second.second;
  long long ans = threes.empty() ? INF : threes.begin()->first;
  auto tov = g[v].begin();
  for (int i = 0; i < min(3, (int)g[v].size()); i++, tov++) {
    auto tou = g[u].begin();
    for (int j = 0; j < min(3, (int)g[u].size()); j++, tou++)
      if (tov->second != u && tou->second != v && tov->second != tou->second)
        ans = min(ans, 1LL * tov->first + tou->first);
  }
  auto it = edges.begin();
  while (it != edges.end()) {
    if (it->second.first != v && it->second.second != v &&
        it->second.first != u && it->second.second != u) {
      ans = min(ans, 1LL * w + it->first);
      break;
    }
    it++;
  }
  return ans;
}
void solve() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int v, u, w;
    scanf("%d %d %d", &v, &u, &w);
    add(v, u, w);
  }
  printf("%lld\n", calcAns());
  int q;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    int t, v, u;
    scanf("%d %d %d", &t, &v, &u);
    if (t == 1) {
      int w;
      scanf("%d", &w);
      add(v, u, w);
    } else {
      del(v, u);
    }
    printf("%lld\n", calcAns());
  }
}
int main() {
  int tt = 1;
  while (tt--) {
    solve();
  }
  return 0;
}

### Prompt

Please create a solution in CPP to the following problem:

You are given an undirected weighted graph, consisting of n vertices and m edges.

Some queries happen with this graph:

  * Delete an existing edge from the graph. 
  * Add a non-existing edge to the graph. 



At the beginning and after each query, you should find four different vertices a, b, c, d such that there exists a path between a and b, there exists a path between c and d, and the sum of lengths of two shortest paths from a to b and from c to d is minimal. The answer to the query is the sum of the lengths of these two shortest paths. The length of the path is equal to the sum of weights of edges in this path.

Input

The first line contains two integers n and m (4 ≤ n, m ≤ 10^5) — the number of vertices and edges in the graph respectively.

Each of the next m lines contain three integers v, u, w (1 ≤ v, u ≤ n, v ≠ u, 1 ≤ w ≤ 10^9) — this triple means that there is an edge between vertices v and u with weight w.

The next line contains a single integer q (0 ≤ q ≤ 10^5) — the number of queries.

The next q lines contain the queries of two types:

  * 0 v u — this query means deleting an edge between v and u (1 ≤ v, u ≤ n, v ≠ u). It is guaranteed that such edge exists in the graph. 
  * 1 v u w — this query means adding an edge between vertices v and u with weight w (1 ≤ v, u ≤ n, v ≠ u, 1 ≤ w ≤ 10^9). It is guaranteed that there was no such edge in the graph. 



It is guaranteed that the initial graph does not contain multiple edges.

At the beginning and after each query, the graph doesn't need to be connected.

It is guaranteed that at each moment the number of edges will be at least 4. It can be proven, that at each moment there exist some four vertices a, b, c, d such that there exists a path between vertices a and b, and there exists a path between vertices c and d.

Output

Print q + 1 integers — the minimal sum of lengths of shortest paths between chosen pairs of vertices before the queries and after each of them.

Example

Input


6 6
1 3 6
4 3 1
1 4 1
2 6 4
2 4 2
5 4 3
4
1 2 5 2
0 1 4
0 3 4
1 6 1 3


Output


4
3
3
7
5

Note

Before the queries you can choose vertices (a, b) = (3, 2) and (c, d) = (1, 4). The sum of lengths of two shortest paths is 3 + 1 = 4.

After the first query you can choose vertices (a, b) = (2, 5) and (c, d) = (1, 4). The sum of lengths of two shortest paths is 2 + 1 = 3.

After the second query you can choose vertices (a, b) = (3, 4) and (c, d) = (2, 5). The sum of lengths of two shortest paths is 1 + 2 = 3.

After the third query, you can choose vertices (a, b) = (2, 6) and (c, d) = (4, 5). The sum of lengths of two shortest paths is 4 + 3 = 7.

After the last query you can choose vertices (a, b) = (1, 6) and (c, d) = (2, 5). The sum of lengths of two shortest paths is 3 + 2 = 5.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
const int M = N + 7;
const double EPS = 1e-10;
const int MOD = 1e9 + 7;
const long long INF = 2e18;
const long long K = 1e6;
set<pair<int, int>> g[M];
set<pair<int, pair<int, int>>> edges;
map<long long, int> p;
map<long long, long long> vals;
multiset<pair<long long, int>> threes;
pair<bool, bool> isImportant(int v, int u) {
  int w = p[v * K + u];
  auto itv = g[v].begin();
  auto itu = g[u].begin();
  bool flagv = false, flagu = false;
  for (int i = 0; i < 3; i++) {
    flagv |= v && (itv == g[v].end() || itv->first > w ||
                   (itv->first == w && u <= itv->second));
    flagu |= u && (itu == g[u].end() || itu->first > w ||
                   (itu->first == w && v <= itu->second));
    if (itv != g[v].end()) itv++;
    if (itu != g[u].end()) itu++;
  }
  return {flagv, flagu};
}
set<pair<int, int>>::iterator getThird(int v) {
  auto it = g[v].begin();
  for (int i = 0; i < min((int)g[v].size(), 2); i++, it++) {
  }
  return it;
}
long long calcSumThree(int v) {
  if ((int)g[v].size() < 3) return INF;
  auto it = g[v].begin();
  long long cur = 0;
  for (int i = 0; i < 3; i++, it++) cur += it->first;
  return vals[v] = cur;
}
void threesIns(const pair<long long, int>& x) {
  if (x.first != INF) threes.insert(x);
}
void threesErs(const pair<long long, int>& x) {
  if (x.first != INF) threes.erase(x);
}
void add(int v, int u, int w) {
  p[v * K + u] = w;
  p[u * K + v] = w;
  pair<bool, bool> imp = isImportant(v, u);
  if (imp.first && imp.second) edges.insert({w, {min(v, u), max(v, u)}});
  if (imp.first) {
    auto itv = getThird(v);
    if (itv != g[v].end() && isImportant(v, itv->second).second)
      edges.erase({itv->first, {min(v, itv->second), max(v, itv->second)}});
    threesErs({vals[v], v});
  }
  if (imp.second) {
    auto itu = getThird(u);
    if (itu != g[u].end() && isImportant(u, itu->second).second)
      edges.erase({itu->first, {min(u, itu->second), max(u, itu->second)}});
    threesErs({vals[u], u});
  }
  g[v].insert({w, u});
  g[u].insert({w, v});
  if (imp.first) threesIns({calcSumThree(v), v});
  if (imp.second) threesIns({calcSumThree(u), u});
}
void del(int v, int u) {
  int w = p[v * K + u];
  pair<bool, bool> imp = isImportant(v, u);
  g[v].erase({w, u});
  g[u].erase({w, v});
  if (imp.first && imp.second) edges.erase({w, {min(v, u), max(v, u)}});
  if (imp.first) {
    auto itv = getThird(v);
    if (itv != g[v].end() && isImportant(v, itv->second).second)
      edges.insert({itv->first, {min(v, itv->second), max(v, itv->second)}});
    threesErs({vals[v], v});
    threesIns({calcSumThree(v), v});
  }
  if (imp.second) {
    auto itu = getThird(u);
    if (itu != g[u].end() && isImportant(u, itu->second).second)
      edges.insert({itu->first, {min(u, itu->second), max(u, itu->second)}});
    threesErs({vals[u], u});
    threesIns({calcSumThree(u), u});
  }
}
void print_info(int n, ostream& os) {
  os << "----------------------------------------\n";
  os << "INFO:\n";
  os << "\nThrees:\n";
  for (auto it : threes) os << it.first << ' ' << it.second << "\n";
  os << "\nEdges:\n";
  for (auto it : edges)
    os << it.first << ' ' << it.second.first << ' ' << it.second.second << "\n";
  os << "\nGraph\n";
  for (int v = 1; v <= n; v++) {
    os << "   " << v << " | ";
    for (auto to : g[v]) {
      os << to.first << ' ' << to.second << " | ";
    }
    os << "\n";
  }
  os << "----------------------------------------\n";
}
long long calcAns() {
  int w = edges.begin()->first;
  int v = edges.begin()->second.first;
  int u = edges.begin()->second.second;
  long long ans = threes.empty() ? INF : threes.begin()->first;
  auto tov = g[v].begin();
  for (int i = 0; i < min(3, (int)g[v].size()); i++, tov++) {
    auto tou = g[u].begin();
    for (int j = 0; j < min(3, (int)g[u].size()); j++, tou++)
      if (tov->second != u && tou->second != v && tov->second != tou->second)
        ans = min(ans, 1LL * tov->first + tou->first);
  }
  auto it = edges.begin();
  while (it != edges.end()) {
    if (it->second.first != v && it->second.second != v &&
        it->second.first != u && it->second.second != u) {
      ans = min(ans, 1LL * w + it->first);
      break;
    }
    it++;
  }
  return ans;
}
void solve() {
  int n, m;
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; i++) {
    int v, u, w;
    scanf("%d %d %d", &v, &u, &w);
    add(v, u, w);
  }
  printf("%lld\n", calcAns());
  int q;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    int t, v, u;
    scanf("%d %d %d", &t, &v, &u);
    if (t == 1) {
      int w;
      scanf("%d", &w);
      add(v, u, w);
    } else {
      del(v, u);
    }
    printf("%lld\n", calcAns());
  }
}
int main() {
  int tt = 1;
  while (tt--) {
    solve();
  }
  return 0;
}

```