交了整整 2 页，本来想用随机化卡过去的，后来发现我的实现跑得太慢就写正常做法了。
首先发现最优答案对应的四个点只可能有以下两种可能：
- \(a,b\) 间有边，\(c,d\) 间有边，此时答案是 \(a,b\) 边权值加 \(c,d\) 边权值。
- \(a\) 与 \(b,c,d\) 三个点间都有边，此时答案是三条边权值之和。
考虑证明，首先证明每条路径长度都不会超过 \(2\)，因为如果一条路径长度达到了 \(4\)，那么这条路径经过的三个点中必然至少有一个点没被选，把任一端点替换为该点答案都会更优。而如果路径长度等于 \(3\) 且中间两点都被选了，那么相当于存在一条 \(a-c-d-b\) 的链，换成 \((a,c),(b,d)\) 更优。而如果两条路径长度都是 \(2\)，必然有一条路径的中点没被选，因此要么两条路径长度都是 \(1\)，要么一条是 \(2\) 一条是 \(1\) 且 \(2\) 的那条路径的中点是 \(1\) 的那条的一个端点。
第二种情况显然可以对每个点开一个 multiset 维护与其相连的每个点。比较麻烦的是第一种情况，这里有两种做法：
- 随机化。给每个点随机一个 \([0,3]\) 中的颜色，然后相当于从四种颜色中各取一个点计算答案。使用线段树分治维护删边即可。单次随机复杂度 \(n\log n\)。由于每次随机正确的概率为 \(\dfrac{4!}{4^4}=\dfrac{3}{32}\)，并且 \((\dfrac{29}{32})^{150}\) 大概是 \(10^{-7}\) 左右，所以大概随个 \(150\) 次就行了，但是我在时限内最多只能随 \(75\) 次。卡常老哥可以试试。
- 注意到对于三条形如 \((x,a),(x,b),(x,c)\) 的边，以及任意两个点 \(u,v\)，如果 \(u\ne x,v\ne x\)，那么这三条边中至少有一条边与其没有公共点。也就是说与同一个点相连的边我们最多保留三条。因此对于一个集合，我们将其中所有边权从小到大排序依次加边，如果与一个端点相连的边数 \(\ge 3\) 就不加这条边。这样还是 \(O(n)\) 的，但是我们猜测，如果当前集合中涉及到的点数超过某个常数就 break，是 ok 的，写了一下发现过了。总复杂度 \(n\log n\)，不过带个常数。
const int MAXN=2e5;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int n,m,qu;map<int,int>val[MAXN+5];map<int,pii>lst[MAXN+5];
struct qry{int opt,u,v,w;}q[MAXN+5];
int col[MAXN+5];ll v[MAXN+5],res[MAXN+5];
multiset<ll>adj[MAXN+5],tot;
ll calc_v(int x){
if(adj[x].size()<=2)return INF;
return (*adj[x].begin())+(*++adj[x].begin())+(*++ ++adj[x].begin());
}
struct node{int l,r;vector<tuple<int,int,int> >vec;}s[MAXN*4+5];
void build(int k,int l,int r){
s[k].l=l;s[k].r=r;if(l==r)return;int mid=l+r>>1;
build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
void insert(int k,int l,int r,tuple<int,int,int>t){
if(l<=s[k].l&&s[k].r<=r)return s[k].vec.pb(t),void();
int mid=s[k].l+s[k].r>>1;
if(r<=mid)insert(k<<1,l,r,t);else if(l>mid)insert(k<<1|1,l,r,t);
else insert(k<<1,l,mid,t),insert(k<<1|1,mid+1,r,t);
}
ll mn;vector<tuple<int,int,int> >vv;
void add(int u,int v,int w){
for(auto t:vv)if(u!=get<1>(t)&&u!=get<2>(t)&&v!=get<1>(t)&&v!=get<2>(t))
chkmin(mn,w+get<0>(t));
vv.pb(mt(w,u,v));sort(vv.begin(),vv.end());
vector<tuple<int,int,int> >nv;
static int cnt[MAXN+5];int tot=0;
for(auto t:vv){
if(cnt[get<1>(t)]>=4||cnt[get<2>(t)]>=4)continue;
if(tot>=9)break;
nv.pb(t);
if(!cnt[get<1>(t)])tot++;cnt[get<1>(t)]++;
if(!cnt[get<2>(t)])tot++;cnt[get<2>(t)]++;
}
for(auto t:vv)cnt[get<1>(t)]=cnt[get<2>(t)]=0;
vv=nv;
}
void iterate(int k){
ll tmn=mn;vector<tuple<int,int,int> >tv=vv;
for(auto t:s[k].vec)add(get<0>(t),get<1>(t),get<2>(t));
if(s[k].l==s[k].r)chkmin(res[s[k].l],mn);
else iterate(k<<1),iterate(k<<1|1);
mn=tmn;vv=tv;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
q[i].opt=1;scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].w);
val[q[i].u][q[i].v]=val[q[i].v][q[i].u]=q[i].w;
}scanf("%d",&qu);
for(int i=m+1;i<=m+qu;i++){
scanf("%d",&q[i].opt);
if(q[i].opt==0){
scanf("%d%d",&q[i].u,&q[i].v);
q[i].w=val[q[i].u][q[i].v];
}else{
scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].w);
val[q[i].u][q[i].v]=val[q[i].v][q[i].u]=q[i].w;
}
}
memset(res,63,sizeof(res));memset(v,63,sizeof(v));
for(int i=1;i<=n;i++)tot.insert(v[i]);
for(int i=1;i<=m+qu;i++){
tot.erase(tot.find(v[q[i].u]));
tot.erase(tot.find(v[q[i].v]));
if(q[i].opt==0){
adj[q[i].u].erase(adj[q[i].u].find(q[i].w));
adj[q[i].v].erase(adj[q[i].v].find(q[i].w));
}else{
adj[q[i].u].insert(q[i].w);
adj[q[i].v].insert(q[i].w);
}
v[q[i].u]=calc_v(q[i].u);v[q[i].v]=calc_v(q[i].v);
tot.insert(v[q[i].u]);tot.insert(v[q[i].v]);
if(i>=m)chkmin(res[i-m],*tot.begin());
}
build(1,0,qu);set<int>in;
for(int i=1;i<=m+qu;i++){
if(q[i].opt==1)lst[q[i].u][q[i].v]=lst[q[i].v][q[i].u]=mp(i,q[i].w),in.insert(i);
else{
pii pp=lst[q[i].u][q[i].v];
insert(1,max(pp.fi-m,0),i-m-1,mt(q[i].u,q[i].v,q[i].w));
in.erase(in.find(pp.fi));
}
}
for(int x:in)insert(1,max(x-m,0),qu,mt(q[x].u,q[x].v,q[x].w));
mn=INF;iterate(1);
for(int i=0;i<=qu;i++)printf("%lld\n",res[i]);
return 0;
}