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.
#ifndef LOCAL
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#endif

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
//#define int ll

#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define eb emplace_back
#define a first
#define b second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
#ifdef LOCAL
#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl
#else
#define dmp(x) void(0)
#endif

template<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}
template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class t,class u>
ostream& operator<<(ostream& os,const pair<t,u>& p){
	return os<<"{"<<p.a<<","<<p.b<<"}";
}

template<class t> ostream& operator<<(ostream& os,const vc<t>& v){
	os<<"{";
	for(auto e:v)os<<e<<",";
	return os<<"}";
}

#define mp make_pair
#define mt make_tuple
#define one(x) memset(x,-1,sizeof(x))
#define zero(x) memset(x,0,sizeof(x))
#ifdef LOCAL
void dmpr(ostream&os){os<<endl;}
template<class T,class... Args>
void dmpr(ostream&os,const T&t,const Args&... args){
	os<<t<<" ";
	dmpr(os,args...);
}
#define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)
#else
#define dmp2(...) void(0)
#endif

using uint=unsigned;
using ull=unsigned long long;

template<class t,size_t n>
ostream& operator<<(ostream&os,const array<t,n>&a){
	return os<<vc<t>(all(a));
}

template<int i,class T>
void print_tuple(ostream&,const T&){
}

template<int i,class T,class H,class ...Args>
void print_tuple(ostream&os,const T&t){
	if(i)os<<",";
	os<<get<i>(t);
	print_tuple<i+1,T,Args...>(os,t);
}

template<class ...Args>
ostream& operator<<(ostream&os,const tuple<Args...>&t){
	os<<"{";
	print_tuple<0,tuple<Args...>,Args...>(os,t);
	return os<<"}";
}

template<class t>
void print(t x,int suc=1){
	cout<<x;
	if(suc==1)
		cout<<"\n";
	if(suc==2)
		cout<<" ";
}

ll read(){
	ll i;
	cin>>i;
	return i;
}

vi readvi(int n,int off=0){
	vi v(n);
	rep(i,n)v[i]=read()+off;
	return v;
}

pi readpi(int off=0){
	int a,b;cin>>a>>b;
	return pi(a+off,b+off);
}

template<class t,class u>
void print(const pair<t,u>&p,int suc=1){
	print(p.a,2);
	print(p.b,suc);
}

template<class T>
void print(const vector<T>&v,int suc=1){
	rep(i,v.size())
		print(v[i],i==int(v.size())-1?suc:2);
}

template<class T>
void print_offset(const vector<T>&v,ll off,int suc=1){
	rep(i,v.size())
		print(v[i]+off,i==int(v.size())-1?suc:2);
}

template<class T,size_t N>
void print(const array<T,N>&v,int suc=1){
	rep(i,N)
		print(v[i],i==int(N)-1?suc:2);
}

string readString(){
	string s;
	cin>>s;
	return s;
}

template<class T>
T sq(const T& t){
	return t*t;
}

//#define CAPITAL
void yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<"\n";
	#else
	cout<<"Yes"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void no(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<"\n";
	#else
	cout<<"No"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void possible(bool ex=true){
	#ifdef CAPITAL
	cout<<"POSSIBLE"<<"\n";
	#else
	cout<<"Possible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}
void impossible(bool ex=true){
	#ifdef CAPITAL
	cout<<"IMPOSSIBLE"<<"\n";
	#else
	cout<<"Impossible"<<"\n";
	#endif
	if(ex)exit(0);
	#ifdef LOCAL
	cout.flush();
	#endif
}

constexpr ll ten(int n){
	return n==0?1:ten(n-1)*10;
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

int topbit(signed t){
	return t==0?-1:31-__builtin_clz(t);
}
int topbit(ll t){
	return t==0?-1:63-__builtin_clzll(t);
}
int botbit(signed a){
	return a==0?32:__builtin_ctz(a);
}
int botbit(ll a){
	return a==0?64:__builtin_ctzll(a);
}
int popcount(signed t){
	return __builtin_popcount(t);
}
int popcount(ll t){
	return __builtin_popcountll(t);
}
bool ispow2(int i){
	return i&&(i&-i)==i;
}
ll mask(int i){
	return (ll(1)<<i)-1;
}

bool inc(int a,int b,int c){
	return a<=b&&b<=c;
}

template<class t> void mkuni(vc<t>&v){
	sort(all(v));
	v.erase(unique(all(v)),v.ed);
}

ll rand_int(ll l, ll r) { //[l, r]
	#ifdef LOCAL
	static mt19937_64 gen;
	#else
	static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
	#endif
	return uniform_int_distribution<ll>(l, r)(gen);
}

template<class t>
void myshuffle(vc<t>&a){
	rep(i,si(a))swap(a[i],a[rand_int(0,i)]);
}

template<class t>
int lwb(const vc<t>&v,const t&a){
	return lower_bound(all(v),a)-v.bg;
}

vvc<int> readGraph(int n,int m){
	vvc<int> g(n);
	rep(i,m){
		int a,b;
		cin>>a>>b;
		//sc.read(a,b);
		a--;b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	return g;
}

vvc<int> readTree(int n){
	return readGraph(n,n-1);
}

template<class Query>
struct chronological_segtree{
	int n,s;
	vvc<Query> qs;
	chronological_segtree(int nn){
		n=nn;
		s=1;
		while(s<n)s*=2;
		qs.resize(s*2);
	}
	void add(int l,int r,Query q){
		for(l+=s,r+=s;l<r;l>>=1,r>>=1){
			if (l&1){
				qs[l].pb(q);
				l++;
			}
			if (r&1){
				r--;
				qs[r].pb(q);
			}
		}
	}
	template<class F,class G,class H,class I>
	void solve(F f,G snapshot,H rollback,I getans){
		auto rec=[&](auto self,int i,int l,int r)->void{
			auto ss=snapshot();
			for(const auto&q:qs[i])
				f(q);
			if(i<s){
				self(self,i*2,l,(l+r)/2);
				self(self,i*2+1,(l+r)/2,r);
			}else if(i-s<n){
				getans(i-s);
			}
			rollback(ss);
		};
		rec(rec,1,0,s);
	};
};

const int Buf=5*ten(6);
int* ptr[Buf],valbuf[Buf];
int used;

void save(int&a){
	ptr[used]=&a;
	valbuf[used]=a;
	used++;
}

ll ans=infLL;
pair<int,ll> snapshot(){
	return mp(used,ans);
}

void rollback(pair<int,ll> unko){
	while(unko.a<used){
		used--;
		*ptr[used]=valbuf[used];
	}
	ans=unko.b;
}

const int nmax=100005;

struct Top3{
	int to[3],v[3];
	Top3(){
		rep(i,3)to[i]=-1;
		rep(i,3)v[i]=inf;
	}
	void add(int z,int x){
		rep(i,3){
			if(v[i]>x){
				save(v[i]);
				swap(v[i],x);
				save(to[i]);
				swap(to[i],z);
			}
		}
	}
	ll getval(){
		if(v[2]==inf)return infLL;
		return 0LL+v[0]+v[1]+v[2];
	}
	ll getval2(int x,int y){
		rep(i,3)if(to[i]!=x&&to[i]!=y){
			if(v[i]==inf)return infLL;
			else return v[i];
		}
		assert(false);
	}
} t3[nmax];

void slv(){
	int n,m;cin>>n>>m;
	
	map<pi,pi> es;
	
	rep(_,m){
		int u,v,w;cin>>u>>v>>w;
		u--;v--;
		es[minmax(u,v)]=pi(0,w);
	}
	
	int q;cin>>q;q++;
	
	struct Query{
		int u,v,w;
	};
	
	chronological_segtree<Query> seg(q);
	
	rng(i,1,q){
		int t,u,v;cin>>t>>u>>v;
		u--;v--;
		if(t==0){
			auto itr=es.find(minmax(u,v));
			seg.add(itr->b.a,i,{u,v,itr->b.b});
			es.erase(itr);
		}else{
			int w;cin>>w;
			es[minmax(u,v)]=pi(i,w);
		}
	}
	for(auto [key,val]:es){
		auto [u,v]=key;
		seg.add(val.a,seg.s,{u,v,val.b});
	}
	
	int mnval=inf,mnu=-1,mnv=-1;
	
	auto func=[&](Query z){
		t3[z.u].add(z.v,z.w);
		t3[z.v].add(z.u,z.w);
		chmin(ans,t3[z.u].getval());
		chmin(ans,t3[z.v].getval());
		
		rep(_,2){
			if(mnu!=-1){
				if(mnu!=z.u&&mnu!=z.v){
					chmin(ans,t3[mnu].getval2(z.u,z.v)+z.w);
				}
			}
			swap(mnu,mnv);
		}
		if(mnu!=z.u&&mnv!=z.u&&mnu!=z.v&&mnv!=z.v){
			if(mnval<inf)chmin(ans,ll(mnval)+z.w);
		}
		save(mnval);
		if(chmin(mnval,z.w)){
			save(mnu);
			save(mnv);
			mnu=z.u;
			mnv=z.v;
		}
	};
	
	auto output=[&](int){
		print(ans);
	};
	
	seg.solve(func,snapshot,rollback,output);
}

signed main(){
	cin.tie(0);
	ios::sync_with_stdio(0);
	cout<<fixed<<setprecision(20);
	
	//int t;cin>>t;rep(_,t)
	slv();
}
